为什么堆比二叉树更好地代表优先级队列？ [英] Why heap is better than binary tree to represent a priority queue?

问题描述

在（max）堆中，很容易在 O（1）时间中找到最大的项，但要实际删除它，需要复杂度<$ c $因此，如果从堆的插入和删除都是 O（log（n））。

< （log（n）），在二叉树上表示优先级队列的堆有什么优点？

解决方案

1. 堆使用更少的内存。它们可以实现为数组，因此不存在用于存储指针的开销。 （二叉树可以被实现为一个数组，但是很可能有很多空的间隙，这会浪费更多的空间，比实现它们作为带有指针的节点）。




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




3. 由于堆可以实现为数组，因此获得连续内存的巨大优势，可能仍然在缓存中，而不是访问指向的节点




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

   
   

缺点是使用堆时你不能做二分搜索，但是对于优先级队列你不需要这个能力。

In a (max) heap it is easy to find the biggest item in O(1) time, but to actually remove it you need complexity of O(log(n)).

So if the insertion and deletion from a heap is both O(log(n)), what are the advantages of a heap over binary tree for representing a priority queue?

解决方案

1. Heaps use less memory. They can be implemented as arrays and thus there is no overhead for storing pointers. (A binary tree CAN be implemented as an array, but there is likely to be many empty "gaps" which could waste even more space than implementing them as nodes with pointers).

2. Heaps are guaranteed to have height of log(n), because they do not need to guarantee that elements can be retrieved in sorted order though an in-order traversal, only that a node's value dominates its children's values. This allows them to have their "packed" structure as an array. A binary tree (unless it is a balanced binary tree) will usually end up with with branches that have a height larger than log(n), so even though operations have the same big O complexity, in reality the heap will be slightly faster.

3. Since the heap can be implemented as an array you get a huge advantage of accessing contiguous memory that is likely still in the cache rather than accessing nodes pointed to by pointers who's memory is scattered all over the place.

4. Heaps are simpler to implement than binary trees (especially balanced binary trees)

A disadvantage is that with heaps you are not able to do a binary search, but for a priority queue you do not need this ability.

这篇关于为什么堆比二叉树更好地代表优先级队列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！