为什么堆比二叉树更好地表示优先级队列？

Question

在(最大)堆中,很容易及时找到最大的项目O(1),但要实际删除它,您需要复杂性O(log(n)).

因此,如果从堆中插入和删除两者O(log(n)),堆超过二叉树表示优先级队列的优点是什么？

Answer 1

1. 堆使用更少的内存.它们可以实现为数组,因此不存在存储指针的开销.(二叉树可以作为一个数组实现,但是可能会有许多空的"间隙",这可能比将它们作为带指针的节点实现更多空间.

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

3. 由于堆可以作为一个数组实现,因此您可以获得很大的优势,即访问可能仍在缓存中的连续内存,而不是访问指针所指向的节点,这些指针的内存遍布整个地方.

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

缺点是使用堆不能进行二进制搜索,但对于优先级队列,您不需要此功能.