在（最大）堆中，很容易找到最大的项目O(1)时间，但要真正删除它，你需要复杂性O(log(n)).
因此，如果从堆中插入和删除都是O(log(n))，用堆来表示优先级队列比二叉树有什么优点？
堆使用较少的内存。它们可以作为数组实现，因此没有存储指针的开销。 （二叉树可以实现为数组，但可能存在许多空的“间隙”，这可能比将它们实现为带有指针的节点浪费更多的空间）。
堆保证具有 log(n) 的高度，因为它们不需要保证可以通过中序遍历按排序顺序检索元素，只需保证节点的值支配其子节点的值即可。这允许它们将其“打包”结构作为数组。二叉树（除非它是平衡二叉树）通常会以高度大于 log(n) 的分支结束，因此即使操作具有相同的大 O 复杂度，实际上堆也会稍微快一些。
由于堆可以实现为数组，因此您可以访问可能仍在缓存中的连续内存，而不是访问内存分散在各处的指针所指向的节点，从而获得巨大的优势。
堆比二叉树（尤其是平衡二叉树）更容易实现
缺点是对于堆，您无法进行二分搜索，但对于优先级队列，您不需要这种能力。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
