data-structures - 为什么堆比二叉树更能代表优先级队列？

Question

在（最大）堆中，很容易及时找到最大的项目O(1)，但要真正删除它，您需要O(log(n)).

因此，如果从堆中插入和删除都是O(log(n))，那么在表示优先级队列方面，堆相对于二叉树的优势是什么？

Answer 1

1. 堆使用更少的内存。它们可以实现为数组，因此存储指针没有开销。（二叉树可以实现为数组，但可能有许多空的“间隙”，这可能比将它们实现为带有指针的节点浪费更多的空间）。

2. 堆保证具有 log(n) 的高度，因为它们不需要保证可以通过中序遍历按排序顺序检索元素，只需保证节点的值支配其子节点的值。这允许他们将“打包”结构作为一个数组。二叉树（除非它是平衡二叉树）通常会以高度大于 log(n) 的分支结束，因此即使操作具有相同的大 O 复杂度，实际上堆会稍微快一些。

3. 由于堆可以实现为数组，因此您可以获得巨大的优势，即访问可能仍在缓存中的连续内存，而不是访问内存分散在各处的指针指向的节点。

4. 堆比二叉树（尤其是平衡二叉树）更容易实现

一个缺点是使用堆你不能进行二分查找，但是对于优先级队列你不需要这个能力。