除了优先级队列的明显答案之外，堆什么时候对我的编程冒险有用？
问问题
56169 次
6 回答
137
每当您需要快速访问最大（或最小）项目时使用它，因为该项目将始终是数组中的第一个元素或树的根。
但是，数组的其余部分保持部分未排序。因此，即时访问只能访问最大（最小）的项目。插入速度很快，因此它是处理传入事件或数据的好方法，并且始终可以访问最早/最大的。
对优先级队列、调度程序（需要最早的项目）等很有用......
堆是一棵树，其中父节点的值大于其任何后代节点的值。
如果您将堆视为按深度以线性顺序存储的二叉树，首先是根节点（然后是该节点的子节点，然后是这些节点的子节点）；那么索引 N 处的节点的子节点位于 2N+1 和 2N+2 处。此属性允许按索引快速访问。而且由于堆是通过交换节点来操作的，这允许就地排序。
于 2009-04-14T20:22:41.343 回答
66
堆是旨在允许快速访问 min 或 max 的结构。
但你为什么要这样？您可以检查add上的每个条目，看看它是最小的还是最大的。这样你总是在恒定时间内拥有最小或最大的O(1)。
答案是因为堆可以让你拉出最小的或最大的并快速知道下一个最小的或最大的。这就是为什么它被称为优先队列。
现实世界的例子（虽然不是很公平的世界）：
假设您有一家医院，根据患者的年龄来就诊。无论他/她什么时候排队，最年长的总是先参加。
你不能只跟踪最老的，因为如果你把他/她拉出来，你不知道下一个最老的。为了解决这个医院问题，你实现了一个最大堆。根据定义，这个堆是部分有序的。这意味着您无法按年龄对患者进行排序，但您知道最老的始终排在最前面，因此您可以在恒定时间内拉出患者O(1)并在 log time 中重新平衡堆O(log N)。
更复杂的例子：
假设您有一个整数序列，并且您想要跟踪median. 中位数是有序数组中间的数字。
例子：
[1, 2, 5, 7, 23, 27, 31]
在上述情况下，7是中位数，因为包含较小数字的数组与包含较大数字的数组[1, 2, 5]大小相同[23, 27, 31]。通常，如果数组有奇数个元素，则中位数是中间 2 个元素的算术平均值，例如(5 + 7)/2.
现在，您如何跟踪中位数？通过有 2 个堆，一个包含小于当前中位数的数字的最小堆和一个包含大于当前中位数的数字的最大堆。现在，如果这些堆总是平衡的，则 2 个堆将包含相同数量的元素，或者一个堆将比另一个堆多 1 个元素，最多。
向序列中添加新元素时，如果数字小于当前中位数，则将其添加到最小堆中，否则将其添加到最大堆中。现在，如果堆不平衡（一个堆的元素多于另一个），则从最大堆中拉出一个元素并添加到最小堆中。现在他们平衡了。
于 2017-01-19T17:45:37.897 回答
14
堆的特点是它是一种保持数据半序的结构；因此，在维持完整秩序的成本和通过随机混沌搜索的成本之间是一个很好的权衡。该特性用于许多算法，例如选择、排序或分类。
堆的另一个有用特性是它可以从数组就地创建！
于 2009-04-14T20:27:57.823 回答
4
也适用于选择算法（找到最小值或最大值）
于 2009-04-14T20:23:31.967 回答
4
任何时候对临时列表进行排序时，都应该考虑堆。
于 2009-04-14T20:33:22.597 回答
1
当您想分别访问最小和最大元素时，可以使用 minHeap 或 maxHeap。
于 2015-10-05T05:52:43.853 回答