为什么堆比二叉树更适合表示优先队列？

Question

9

在最大堆中，查找最大项很容易且时间复杂度为O(1)，但是要删除它则需要O(log(n))的复杂度。因此，如果从堆中插入和删除都是O(log(n))，那么用堆表示优先队列有什么优势，而不是用二叉树呢？

- Shelef

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mclaassen · Accepted Answer

堆使用更少的内存。它们可以作为数组实现，因此没有存储指针的开销。(二叉树也可以作为数组实现，但可能会有许多空的“间隙”，这可能会浪费比使用带指针的节点更多的空间)。
堆保证高度为log（n），因为它们不需要保证元素可以通过中序遍历以排序的顺序检索，只需要保证一个节点的值优于其子节点的值。这使得他们的“紧凑”结构可以作为数组。普通的二叉树（除非是平衡的二叉树）通常会出现具有比log（n）更大高度的分支，因此尽管操作具有相同的大O复杂度，但实际上堆将稍微快一些。
由于堆可以作为数组实现，因此您可以获得访问连续内存的巨大优势，这些内存很可能仍在缓存中，而不是访问由散布在各处的指针指向的节点所占用的内存。
堆比二叉树(特别是平衡的二叉树)更容易实现。

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