堆数据结构有什么用？
我正在做一些涉及堆的作业，并且我了解它们的结构。堆必须具有满足堆属性的每个节点，
最大堆属性是 除根之外的每个节点， 堆[Parent(i)] >= 堆[i]
因此在每个节点，较高的节点具有较高的编号，较低的节点具有较低的编号。我明白这一点。但除了简单地获取列表中最高的 n 个数字之外，我看不到堆的用途。我没有看到一种简单的方法来搜索特定值并返回节点，或者搜索 n 个最低数字（在最大堆中）。两者在二叉搜索树中都相对容易。
为什么不使用简单的二叉搜索树呢？或者更好的是平衡二叉搜索树？
编辑： 我应该指出，这并不是寻找家庭作业问题的答案。实际的家庭作业问题是为 insert() 和 extractMax() 函数编写并行 p-堆的伪代码。我已经回答了他们。他们只是让我意识到我并不真正理解堆。
I'm working on some homework involving Heaps, and I understand how they are structured. A heap must have each node satisfying the heap property,
the max-heap property is that for
every node i other then the root,
Heap[Parent(i)] >= Heap[i]
So at each node, the higher nodes have higher numbers, lower nodes have lower numbers. I understand this. But I can't see a use of a Heap other then to simply get the highest n numbers in a list. I don't see an easy way to search for a particular value and return the node, or to search for the n lowest number (in a max-heap). Both are relatively easy in a binary search tree.
Why wouldn't you just use a simple binary search tree? Or better yet, a balanced binary search tree?
EDIT:
I should note, that this is not looking for an answer to a homework problem. The actual homework problem was writing pseudocode for parallel-p-heap for the insert() and extractMax() functions. And I already answered them. They just made me realize that I don't really understand Heaps.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
堆数据结构有很多应用。
完全和几乎完全的二进制堆可以单独使用数组以非常节省空间的方式表示。第一个（或最后一个）元素将包含根。数组的接下来的两个元素包含其子元素。接下来的四个包含两个子节点的四个子节点，依此类推。因此，位置 n 处的节点的子节点将位于基于 1 的数组中的位置 2n 和 2n+1，或者位于基于 1 的数组中的 2n+1 和 2n+2。从零开始的数组。这允许通过执行简单的索引计算来向上或向下移动树。平衡堆是通过交换无序的元素来完成的。由于我们可以从数组构建堆，而不需要额外的内存（例如，对于节点），因此堆排序可用于就地对数组进行排序。
在某些应用中，堆相对于树的另一个优点是，可以使用 Tarjan 算法在线性时间内完成堆的构建。
参考：http://en.wikipedia.org/wiki/Heap_%28data_struct%29< /a>
The heap data structure has many applications.
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
由于缺少指针（堆通常使用基于数组的数据结构），操作往往比二叉树更快。此外，一些更复杂的堆（例如二项式）可以有效地合并，这对于二叉树来说并不容易做到。 这个问题也提供了信息。
Because of the lack of pointers (heaps typically use an array-based data structure), the operations tend to be faster than for a binary tree. Also, some more complicated heaps (such as binomial) can be merged efficiently, which isn't easy to do for a binary tree. There is also information available at this SO question.