7

在我看来，堆优于二叉树的唯一优势是在 O(1) 的复杂度中找到堆中的最小项，而不是在二叉树中的 O(log(2)n)。

在实现优先级队列时，您需要从数据结构中删除每个最小的项目。从树中删除最小的项目，并且两个堆都以 O(log(2)n) 的复杂度完成。虽然从树中删除项目可能更复杂。删除没有子项的项目实际上非常简单。

我的问题是为什么在实现优先级队列时使用堆而不是二叉树（在这种情况下更简单）？

4

5 回答 5

11

当二叉树收敛到一个数组时，二叉树的最坏情况复杂度将是 O(n)，而在堆中它仍然是 O(log(n))。您可以使用平衡二叉树，如红黑或 AVl，但它会变得更复杂，需要更多内存。

于 2013-03-26T19:46:31.803 回答
5

堆通常比适当平衡的二叉树更容易实现。此外，它们需要更少的内存开销（元素可以直接存储在数组中，而无需分配树节点和指针等所有内容），可能更快的性能（主要是由于使用单个连续数组的内存局部性）......为什么你不会使用它们吗？

于 2013-03-26T19:58:42.110 回答
5

您的首选应该取决于预期的访问模式，以及您可能存储的数据量：...

  • 如果没有太多数据（例如，n 小于 30），那么未排序的数组就可以了；
  • 如果你几乎从不添加、删除或更新，排序数组就可以了；
  • 如果 n 小于 100 万，并且您只搜索顶部元素（排名第一或最后的元素），堆会做得很好（特别是如果您经常更新随机选择的元素，因为您在缓存的 LRU（最近最少使用）队列中执行，因为平均而言，这样的更新是 O(1)，而不是 O(log(n)))
  • 如果 n 小于 100 万，并且您不确定要搜索什么，那么平衡树（例如，红黑或 AVL）就可以了；
  • 如果 n 很大（比如 100 万以上），那么使用 b-tree 或 trie 可能会更好（一旦 n 足够大，平衡二叉树的性能往往会“跌落悬崖”：内存访问往往过于分散，缓存未命中真的开始受到伤害）

...但我建议您尽可能保持该选项处于打开状态，以便您可以对至少一个备选方案进行基准测试并切换到它，如果它表现更好的话。

在过去的 20 年里，我只在两个应用程序中工作过，堆是任何事物的最佳选择（一次用于 LRU，一次用于令人讨厌的运筹学应用程序，恢复随机扰动的 k 维超立方体的可加性，其中大多数超立方体中的细胞出现在 k 个不同的堆中，并且内存非常宝贵）。然而，在这两种情况下，它们的表现都比其他选择好得多：实际上比平衡树或 b 树快几十倍。

对于我在上一段中提到的超立方体问题，我的团队负责人认为红黑树的性能会比堆好，但基准测试表明红黑树的速度要慢得多（我记得，它们慢了大约 20 倍） )，虽然 b-trees 明显更快，但堆也轻松地击败了它们。

在我上面提到的两种情况下，堆的重要特征不是 O(1) 查找最小值，而是随机选择的元素的 O(1) 平均更新时间。

-James Barbetti（好吧，我以为我是。但验证码一直告诉我我不是人类）

于 2013-04-22T11:18:46.107 回答
0

如果您经常使用查找或搜索操作，则首选平衡二叉树。由于这个原因，线段相交代码使用平衡树而不是堆。

于 2013-07-25T05:53:13.447 回答
0

首先有不同的二叉树（其中一些非常困难，其中一些只提供 average O(log n)），堆就是其中之一。

第二：虽然对大多数树的操作是O(log n)，但它们更复杂，有常数因子。

堆需要恒定的额外内存，而树通常需要在每个节点中存储指针。

顺便说一句，堆非常简单，只使用数组（我不确定它是否在 Java 中以这种方式实现，但我确实这么认为）

于 2013-03-26T19:40:07.537 回答