c++ - 为什么优先级队列实现为二叉堆？

Question

为什么人们强调堆是用来实现优先级队列的，因为查看最大/最小值的时间复杂度是 O(1) 。
通过使用指针指向最右边/最左边的节点，这也不能很容易地在 bst 上实现吗？

Answer 1

鉴于您提出基于 BST 的优先级队列，我将尝试向您解释为什么堆优于 BST。

堆是一棵完整的树；它是一棵完美平衡的树。它的高度是 log_2(n+1)。

如果此方法是平衡的，则 BST 方法是值得的。维持 BST 平衡的最著名技术是 AVL 树。这种树的高度范围为 1.44 log_2(n+2) - 0.33。

对于最小值的咨询，BST 的成本为 O(log(n))，而堆的成本为 O(1)。因此对于此操作，堆显然更好。

对于插入和删除，成本是渐近等价的。但是 BST 往往更昂贵，因为它的高度往往高于完美平衡的树。此外，AVL 树比堆消耗更多的常数时间。在 AVL(以及其他平衡方法、红黑树、treaps、splays 等)中，您执行旋转，而在堆中执行交换，这比旋转更便宜。

BST 上的删除是一项复杂且代价高昂的操作，可能需要 O(log(n)) 循环。堆是 O(log(n)) 交换，召回比轮换更便宜。

最终，在插入的情况下，您可以为堆执行 O(log(n)) 交换，并为 AVL 执行最多两次旋转。但是随着插入到 AVL 中，您需要执行不成功的搜索，而堆中您可以在开始交换之前直接插入新 key 。我认为只有插入 BST 有时才能击败堆。但是，请考虑到您很可能会使用优先级队列进行咨询和删除；所以，如果是这种情况，那么您肯定会恢复在进行插入时可能损失的时间。

此外，如果使用存储完整树的层级遍历的数组，堆比 BST 更容易实现。在这种情况下，您不需要指针