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

Question

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

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

Answer 1

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

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

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

堆比二叉树(尤其是平衡二叉树)更容易实现

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