堆通是一种近似的完全二叉树，树上每一个结点对应数组中的一个元素。除最底层外，该树是完全充满的，且最底层的元素从左往右填入。

设计目的
: 在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

逻辑定义

n个元素序列{k1, k2… ki…kn},当且仅当满足下列关系时称之为堆：
(ki <= k2i, ki <= k2i+1)或者(ki >= k2i, ki >= k2i+1), (i = 1, 2, 3, 4… n/2)

堆的结构

一个堆结构将由一个数组和一个代表当前堆大小的整数组成。

堆序性质

使操作被快速执行的性质是堆序性质(heap-order-property)。由于我们想要能够快速地找出最小元， 因此最小元应该在根上。如果考虑任意子树也应该是一个堆，那么任意节点就应该小千它的所有后裔。

应用这个逻辑， 我们得到堆序性质。在一个堆中，对于每一个节点X,X的父亲中的关键字小于（或等于）X中的关键字，根节点除外（它没有父亲）。在图6.5中左边的树是一个堆，但是，右边的树则不是（虚线表示堆的有序性被破坏）。

根据堆序性质， 最小元总可以在根处找到。因此，我们以常数时间得到附加操作丘find.Min。

堆操作

其他的堆操作

decreaseKey（降低关键字的值）
: decreaseKey(p,Δ)操作降低在位置p处的项的值，降低的幅度为正的量Δ。由于这可能破坏堆序性质，因此必须通过上滤对堆进行调整。该操作对系统挂历程序是有用的：系统管理程序能够使他们的程序以最高的优先级来运行。

increaseKey（增加关键字的值）
: increaseKey(p,Δ)操作增加在位置p处的值，增值的幅度为正的量Δ。这可以用下滤来完成。许多调度程序自动降低正在过多地小号CPU时间的进程的优先级。

为将元素X插入堆中，找到空闲位置，创建一个空穴，若满足堆序性（英文：heap order），则插入完成；否则将父节点元素装入空穴，删除该父节点元素，完成空穴上移。直至满足堆序性。这种策略叫做上滤（percolate up）。

删除该节点元素后，队列最后一个元素必须移动到堆得某个位置，使得堆仍然满足堆序性质。这种向下替换元素的过程叫作下滤。

最小-最大堆的插入

最小-最大堆：各层交替为最小层和最大层的堆。

最大层：该层上的节点大于等于以其为根节点的子树上的所有节点。

最小层：该层上的节点小于等于以其为根节点的子树上的所有节点。

本文中，我们令堆的层数从1开始，节点编号也从1开始，即根节点为第1层，编号为1。

最小最大对具有如下性质：

对于任一节点，从该节点到叶节点的任意一条路径，

（1）处于最小层的节点关键字逐渐增大；

（2）处于最大层的节点关键字逐渐减小；

（3）所有处于最大层的节点关键字大于所有处于最小层的节点的关键字。

具体实现见下面，我们使用min_max_insert将item插入到堆heap中，插入前节点个数为*n。边界条件不进行详细解释。

首先将item存入heap[*n+1]处，检查该元素的父节点是最大层还是最小层。

1）父节点是最小层，且该元素小于父节点

该节点是最后一个节点且处于最大层，本次插入只增加最大层节点数，最小层节点数不变；

父节点是最小层的最后一个元素，是最小层节点中最大的节点；

假设插入前最小层节点数为ms，最大层节点数为mt，则插入后最小层节点数不变，最小层节点数为mt+1。由推论可知，最小层节点是所有节点中最小的前ms个节点，父节点属于这ms个节点中最大的节点，现在新插入的节点小于父节点，就意味着，新节点将代替父节点成为最小的前ms个节点之一，因此父节点属于最大层节点。

又由于父节点原先小于最小层，因此小于所有原先最大层的节点，现在转入最大层后，成为最大层节点中最小的节点，根据最小最大堆的性质可知，父节点必属于其所属路径上的最后一个节点。因此我们直接把父节点放入heap[*n+1]处即可。

对于新加入节点，我们不需要改动其它路径，只需沿着heap[*n+1]到根节点的这条路径，找出所有最小层节点，将其放在某位置，使得该路径上节点顺序满足最小最大堆性质(1)即可。

2）父节点是最小层，且该元素大于父节点

同理，新加入节点只是改变了最大层节点数，不会改变最小层节点数。

父节点是前ms个最小节点中最大的，新节点大于父节点，所以新节点不可能是前ms个最小节点，所以新节点属于最大层。

因此，我们只需找出heap[*n+1]到根节点的这条路径上所有最大层节点，将新节点放入某个位置，其它节点依次后移，使得这些节点满足最小最大堆的性质(2).

3）父节点是最大层，且该元素大于父节点

此时，新加入的节点处于最小层，所以新节点的加入改变的是最小层节点数，不会改变最大层节点数。

最大层节点是所有节点中最大的mt个节点，且父节点是则mt个节点中最小的节点，新节点大于父节点，就意味着父节点不可能再成为最大的前mt个节点，所以新节点代替父节点成为最大层节点。

由于父节点大于所有最小层节点，所以父节点应该是出于该路径上的最后一个位置，因此直接将父节点放入heap[*n+1]即可。

对于新节点，只需找出heap[*n+1]到根节点路径上的所有最大层节点，将新节点放入某位置，其它节点依次后移，使得该路径上所有最小层节点满足性质(1)即可。

4）父节点是最大层，且该元素小于父节点

最大层节点不变，仍是原先的mt个节点。

新节点属于最小层节点，将新节点加入heap[n+1]，找出heap[n+1]到根节点路径上所有最小层节点，重新排序，满足性质（1）。

最小-最大堆的删除（最小元素）

基本思想：最小元素就是最小-最大堆根节点对应的元素，所以每次都是直接删除该节点。如果还有剩余节点，接着要做的就是将剩余节点重新组织成一个新的最小-最大堆。

最直接的方式就是对所有元素重新建堆，即把剩余元素逐个输入堆里，每输入一个元素调用一次函数min_max_insert，将已输入元素建成最小-最大堆，直到所有元素输入为止。但这么做显然效率是比较低的，原先的堆里所包含的信息被全部丢弃。直觉告诉我们，可以利用原先堆的信息，找到更简便的方法。

我们现在将剩余节点全部保留在原位置，缺了一个根节点，于是，我们很自然的想到要找一个节点放入根节点位置，我们找到剩余节点中最小的节点放入根节点。

因为最小最大堆的根节点是整个堆中最小的元素，所有首先在剩余节点中找到最小的节点，并将该节点放入根节点处；假设最小节点位置为k。

现在k位置空了下来。另外，现在堆节点数少了一个，最后一个节点需要删除，也就意味着该节点存放的元素将没有位置存放，用item表示，我们很自然地想到，将item放在k位置。那么这么做究竟是否可行呢？通过分析，直接放在有些情况下会违反最小-最大堆，下面我们具体分析：

（1）只剩一个节点，不需进行任何操作（该节点已被放入根节点）；

（2）剩余两个或两个以上节点且k是最后一个节点，不需进行任何操作（该节点已被放入根节点）；

（3）剩余两个或两个以上节点且k不是最后一个节点其它情况，则需要根据k可能出现的位置来进一步分析：

首先，k只可能出现在第二层或第三层（否则不可能是最小节点）。

如果出现在第二层，则有两种可能：左儿子、右儿子。

如果是左儿子，说明左儿子没有子节点，右儿子也没有子节点（完全二叉树），我们只需要将item直接放入k节点处即可；

如果是右儿子，则右儿子没有子节点，左儿子可能有子节点。不管左儿子有没有子节点，都只需将item放入k节点即可；

如果出现在第三层，不管最后一个节点是不是k节点的后代，甚至不管k是否有后代，将item放入k节点后，都只会影响从根节点出发到到叶节点结束，且经过k节点的路径，其它路径仍满足最小最大堆的性质。

我们由最小最大堆的性质和定义可知，检查一个堆是否为最小最大堆，只需检查其各条路径是否满足最小-最大堆性质即可。

违反最小-最大堆有下面几种情况：

item大于k的父节点：我们只需要item和父节点调换，此时其它路径仍不会违反，父节点仍是那些路径上的最大节点。接下来，只需把item（此时已变为原先k的父节点元素）放入k节点，但同样不能直接放入，插入方式与最开始将最后一个元素插入根节点一样。

因为此时k是第三层，其父节点是第二层，为最大层，所以父节点应大于k节点；父节点处于第二层，大于以其为根的堆中所有元素。item既然大于父节点，且即将成为这个堆中的元素之一，因此item是新堆中最大的元素，应将其放在父节点的位置，且不管后面如何排，都不会改变，也就是说，我们接下来只需考虑以k节点及k节点的兄弟为根的子树。另外，以k节点的兄弟为根的子树在父节点和item交换后并不违反最小-最大堆性质，因此，我们只需考虑以k为根的子树。问题就变成了将新的item插入以k为根的子树的根节点（即k节点）。这和最先将最后一个元素插入根节点完全相同。

item大于k的子节点：把item插入k节点，插入方式与最开始将最后一个元素插入根节点一样。

通过上面的分析，item插入以k的父节点为根的堆中后，堆的最大元素仍然是k的父节点，所以父节点不变，因此，k的兄弟节点所在的路径或子堆也未违反最小-最大堆性质，不需改变，所以我们就只考虑将item插入以k为根的堆中的根节点（即k节点）即可。

总结起来就是三种情况：

a) k处于第二层：

b) k处于第三层且item大于k的父节点；

c) k处于第三层且item大于k的子节点；

结合边界条件，我们很容易进行实现。

参考资料

1.中文维基百科——堆 (数据结构))

2.数据结构与算法分析——C++描述版(第四版)

3.最小-最大堆的插入和删除