我什么时候会想用堆？

无论何时需要快速访问最大(或最小)项，都可以使用它，因为该项始终是数组中的第一个元素或树的根。

However, the remainder of the array is kept partially unsorted. Thus, instant access is only possible to the largest (smallest) item. Insertions are fast, so it's a good way to deal with incoming events or data and always have access to the earliest/biggest.

对于优先级队列、调度程序(需要最早的项目)等非常有用。

A heap is a tree where a parent node's value is larger than that of any of its descendant nodes.

如果你把堆想象成一个二叉树，按深度的线性顺序存储，首先是根节点(然后是那个节点的子节点，然后是那些节点的子节点) ; 然后索引 N 处的节点的子节点是2N + 1和2N + 2。此属性允许通过索引快速访问。由于堆是由交换节点操作的，因此可以进行就地排序。

也适用于选择算法(寻找最小值或最大值)

The characteristic of a heap is that it is a structure that maintains data semiordered; thus, it is a good tradeoff between the cost of maintaining a complete order and the cost of searching through random chaos. That characteristic is used on many algorithms, such as selection, ordering, or classification.

Another useful characteristic of a heap is that it can be created in-place from an array!

任何时候对临时列表进行排序时，都应该考虑堆。

当希望分别访问最小和最大的元素时，可以使用 minHeap 或 maxHeap。

堆是允许快速访问 min 或 max 的结构。

但你为什么想要那样？你可以检查 加上的每个条目，看看它是最小的还是最大的。这样你总是有最小或最大的恒定时间 O(1)。

答案是因为 堆允许你拉最小的或者最大的，并且很快知道下一个最小的或者最大的。这就是为什么它被称为优先队列。

现实生活中的例子(尽管不是很公平的世界) :

假设您有一家根据患者年龄进行治疗的医院。最年长的总是第一个被照顾，无论他/她什么时候进入队列。

你不能只是跟踪最老的一个，因为如果你把他/她拉出来，你不知道下一个最老的。为了解决这个医院问题，您实现了一个 最大堆。根据定义，这个堆是部分有序的。这意味着您不能按照年龄对患者进行排序，但是您知道年龄最大的患者总是位于顶部，因此您可以在固定时间 O(1)中拉出患者，并在日志时间 O(log N)中重新平衡堆。

更复杂的例子:

假设您有一个整数序列，并且希望跟踪 median。中位数是位于有序数组中间的数字。

例如:

[1, 2, 5, 7, 23, 27, 31]

在上面的例子中，7是中值，因为包含较小数字 [1, 2, 5]的数组与包含较大数字 [23, 27, 31]的数组的大小相同。通常，如果数组有偶数个元素，中间值是中间两个元素的算术平均值，例如 (5 + 7)/2。

现在，你如何跟踪中间值？分两堆,1分钟堆包含小于当前中值的数字，最大堆包含大于当前中值的数字。现在，如果这些堆总是平衡的，那么这两个堆将包含相同数量的元素，或者一个堆将比另一个多一个元素，最多。

向序列中添加新元素时，如果数字小于当前中值，则将其添加到最小堆中，否则将其添加到最大堆中。现在，如果堆是不平衡的(一个堆比另一个堆多1个元素) ，那么从最大的堆到最小的堆，pull是一个元素。现在它们平衡了。