Heap数据结构的用途是什么？

Question

我正在做一些涉及堆的家庭作业,我理解它们的结构.堆必须让每个节点满足堆属性,

max-heap属性是除了根之外的每个节点,Heap [Parent(i)]> = Heap [i]

因此,在每个节点处,较高节点具有较高数量,较低节点具有较低数量.我理解这一点.但我看不到使用Heap,只是简单地获得列表中最高的n个数字.我没有看到一种简单的方法来搜索特定值并返回节点,或者搜索n个最小数字(在最大堆中).两者在二叉搜索树中相对容易.

你为什么不只使用一个简单的二叉搜索树？或者更好的是,平衡的二叉搜索树？

编辑:我应该注意,这不是寻找家庭作业问题的答案.实际的作业问题是为insert()和extractMax()函数编写parallel-p-heap的伪代码.我已经回答了他们.他们让我意识到我并不真正了解Heaps.

Answer 1

堆数据结构有许多应用程序.

• Heapsort:最好的排序方法之一,没有二次最坏情况.
• 选择算法:使用堆可以在线性时间(通常是恒定时间)内找到最小值,最大值,最小值和最大值,中值,甚至第k个最大元素.[4]
• 图算法:通过使用堆作为内部遍历数据结构,运行时间将按多项式顺序减少.此类问题的示例是Prim的最小生成树算法和Dijkstra的最短路径问题.

完全和几乎完整的二进制堆可以仅使用阵列以非常节省空间的方式表示.第一个(或最后一个)元素将包含根.数组的下两个元素包含其子元素.接下来的四个包含两个子节点的四个子节点等.因此,位置n处的节点的子节点将位于基于一个阵列的位置2n和2n + 1中,或者位于2n + 1和2n + 2中从零开始的数组.这允许通过简单的索引计算来向上或向下移动树.通过交换乱序的元素来完成堆的平衡.由于我们可以从数组构建堆而无需额外的内存(例如,对于节点),因此可以使用heapsort对数组进行就地排序.

在某些应用中,堆叠超过树的另一个优点是使用Tarjan算法可以在线性时间内完成堆的构建.

参考:http://en.wikipedia.org/wiki/Heap_%28data_structure%29

Answer 2

由于缺少指针(堆通常使用基于数组的数据结构),操作往往比二叉树更快.此外,可以有效地合并一些更复杂的堆(例如二项式),这对于二叉树来说并不容易.在这个SO问题上也有可用的信息.