为什么在实现优先级队列时使用堆而不是二叉树？

Question

在我看来,堆超过二叉树的唯一优势是在二进制树中以O(1)而不是O(log(2)n)的复杂度找到堆中的最小项.

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

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

Answer 1

当二叉树收敛到数组时,二进制树情况下的最坏情况复杂度为O(n),而在堆中它保持为O(log(n)).你可以使用平衡的二进制树,如红黑或AVl,但随后它变得更加复杂,需要更多的内存.

Answer 2

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

Answer 3

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

• 如果没有太多数据(比如说n小于30),那么未排序的数组就可以了;
• 如果你几乎从不添加,删除或更新,排序的数组就可以了;
• 如果n小于,比如100万,并且你只是在搜索顶级元素(排名第一或最后一个),那么堆就会很好(特别是如果你经常更新随机选择的元素,就像你一样例如,在LRU(最近最少使用的)队列中执行缓存,因为平均来说这样的更新是O(1),而不是O(log(n)))
• 如果n小于,比如100万,并且你不确定你要搜索的是什么,那么平衡的树(比如红黑或AVL)就可以了;
• 如果n很大(例如100万及以上),你可能会更好地使用b树或者trie(一旦n足够大,平衡二叉树的性能往往会"从悬崖上掉下来":内存访问往往太分散,缓存未命中真的开始受伤)

...但我建议尽可能将选项保持为开放状态,以便您可以对至少一个备选方案进行基准测试并切换到它,如果它表现更好.

在过去的二十年里,我只参与了两个应用程序,其中堆是最好的选择(一次用于LRU,一次用于令人讨厌的操作 - 研究应用程序,恢复对随机扰动的k维超立方体的可加性,其中大多数超立方体中的细胞出现在k个不同的堆中,并且存储器是非常宝贵的.然而,在这两种情况下,它们的表现远远超过其他选择:比平衡树或b树快几十倍.

对于我在上一段中提到的超立方问题,我的团队负责人认为红黑树的表现比堆好,但基准测试显示红黑树的速度比较慢(我记得,它们慢了约20倍)虽然b树明显更快,但是它们也很舒服地击败了它们.

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

-James Barbetti(嗯,我以为我是.但验证码一直告诉我,我不是人类)