10

我正在做一些涉及堆的作业，并且我了解它们的结构。堆必须具有满足堆属性的每个节点，

最大堆属性是对于除根节点之外的每个节点 i，Heap[Parent(i)] >= Heap[i]

所以在每个节点上，较高的节点具有较高的数字，较低的节点具有较低的数字。我明白这一点。但是我看不到使用堆来简单地获取列表中最高的 n 个数字。我没有看到一种简单的方法来搜索特定值并返回节点，或者搜索 n 最小的数字（在最大堆中）。两者在二叉搜索树中都相对容易。

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

编辑：我应该注意，这不是在寻找家庭作业问题的答案。实际的作业问题是为 insert() 和 extractMax() 函数编写并行 p 堆的伪代码。我已经回答了他们。他们只是让我意识到我并不真正了解堆。

4

2 回答 2

13

堆数据结构有很多应用。

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

Full and almost full binary heaps may be represented in a very space-efficient way using an array alone. The first (or last) element will contain the root. The next two elements of the array contain its children. The next four contain the four children of the two child nodes, etc. Thus the children of the node at position n would be at positions 2n and 2n+1 in a one-based array, or 2n+1 and 2n+2 in a zero-based array. This allows moving up or down the tree by doing simple index computations. Balancing a heap is done by swapping elements which are out of order. As we can build a heap from an array without requiring extra memory (for the nodes, for example), heapsort can be used to sort an array in-place.

One more advantage of heaps over trees in some applications is that construction of heaps can be done in linear time using Tarjan's algorithm.

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

于 2011-03-08T12:28:07.587 回答
6

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

于 2011-03-08T03:35:03.477 回答