在最大堆中,查找最大项很容易且时间复杂度为
O(1)
,但是要删除它则需要O(log(n))
的复杂度。因此,如果从堆中插入和删除都是O(log(n))
,那么用堆表示优先队列有什么优势,而不是用二叉树呢?O(1)
,但是要删除它则需要O(log(n))
的复杂度。因此,如果从堆中插入和删除都是O(log(n))
,那么用堆表示优先队列有什么优势,而不是用二叉树呢?堆使用更少的内存。它们可以作为数组实现,因此没有存储指针的开销。(二叉树也可以作为数组实现,但可能会有许多空的“间隙”,这可能会浪费比使用带指针的节点更多的空间)。
堆保证高度为log(n),因为它们不需要保证元素可以通过中序遍历以排序的顺序检索,只需要保证一个节点的值优于其子节点的值。这使得他们的“紧凑”结构可以作为数组。普通的二叉树(除非是平衡的二叉树)通常会出现具有比log(n)更大高度的分支,因此尽管操作具有相同的大O复杂度,但实际上堆将稍微快一些。
由于堆可以作为数组实现,因此您可以获得访问连续内存的巨大优势,这些内存很可能仍在缓存中,而不是访问由散布在各处的指针指向的节点所占用的内存。
堆比二叉树(特别是平衡的二叉树)更容易实现。
缺点是在堆中不能进行二分查找,但是对于优先队列,您不需要这种能力。