16

在创建二元最大堆时，为什么将其实现为基于数组而不是基于树的更好（基于树，每个节点也有一个指向其父节点的指针）？在运行时分析、内存使用、性能...

对于二进制最大堆，运行时间为：

  • 插入：O(lg n)
  • 删除最小值：O(lg n)
  • 合并：O(n)

对于树实现

  • 插入：O(lg n)
  • 删除最小值：O(lg n)
  • 合并：O(n)

谁能详细解释一下？

4

2 回答 2

14

树使用更多的时间和内存。复杂性相同，但常数因素不同。

与基于数组的堆相比，树的指针使用大量内存，在这种堆中，您几乎不需要任何额外的空间，但值本身占用的空间。操纵这些指针也需要时间。分配和释放节点也可能需要一些时间和空间......

此外，不能保证树的节点会在内存中一起出现。如果这两种选择中的任何一种都利用了缓存，那么它就是基于数组的堆。

于 2013-02-06T09:11:57.603 回答
6

参考通过其他人的答案已经说过的话，人们可能想知道为什么我们也不将数组用于 BST。二叉堆要求它应该是一棵完整的二叉树。因此，叶节点的深度始终为 h 或 h-1。我相信正是这个属性使得使用数组成为二叉堆的理想选择，而不适合 BST（因为 BST 没有完整的二叉树要求 - 它可能是严格/完整/完整的）。

于 2015-12-01T17:08:49.090 回答