堆
一、堆的基本概念和性质
堆(heap)是一个完全二叉树，并且满足以下性质：每个节点的值都大于或等于其左右孩子节点的值，称为大根堆；或是每个节点的值都小于或等于其左右孩子的值，称为小根堆。
复习：完全二叉树
设二叉树的深度为h，除第h层外，其它各层（1 ~ h-1）的节点数都达到最大个数，第h层所有的节点都连续集中在最左边，这就是完全二叉树。
完全二叉树：
非完全二叉树：
堆：
从堆的概念不难看出，大根堆堆顶为集合的最大值，小根堆堆顶为集合的最小值
堆的存储
那么在数据结构中，我们如何存储堆呢？由于堆是一个完全二叉树，这就决定了每个节点的相对位置是固定的，所以这里我们不同于以往的用链表来存储，我们采用一种船新的存储方式：用一个一维数组来存储堆。为了方便操作，我们采用下标从1开始，下标1的位置就是根节点，节点x的左儿子是2x,节点x的右儿子是2x + 1
二、堆的两个基本操作（down、up）
1、向上调整法
向上调整法用于除最后一个元素意外，其余节点均满足堆的性质时，我们用向上调整法将最后一个节点调整成堆。具体做法如下（以小跟堆为例）：
从最后一个节点开始，比较该节点和其父节点的大小，如果该节点的值小于父节点的值，则进行交换。一直到该节点到堆顶或者该节点的值大于等于父节点的值时结束。
那么，具体代码该如何实现呢？我们知道了从父亲推出左右儿子的关系为x = 2x 和 x = 2x + 1，那知道当前节点的下标，可以反推其父亲节点的下标。假设该节点下标为u，则其父亲节点下标为u / 2或者是(u - 1) / 2，那经过向下取整的规则后，其父节点下标可以直接写为u / 2,那我们就可以写出代码了。
//h[]为堆（数组）
void up(int u){
while(u > 1 && h[u] ){
swap(h[u], h[u / 2]);
u /= 2;
}
}
2、向下调整法
向下调整法是从上向下调，该方法在建堆，解决排序等问题上有重大作用，所以应当重点掌握。对于采用向下调整法来说，应该满足条件：该根节点左右子树均为大堆或者均为小堆，只有根节点不满足，这时候我们采用向下调整法来将整个树调整成堆。具体做法如下（以小根堆为例）：
从根节点开始，比较该节点与其左右孩子节点的值，如果该节点的值大于孩子节点的值，将其与左右孩子中较小的那个进行交换，一直到该节点为最后一层或者该节点的值小于等于左右孩子节点的值时结束。
代码实现思路：从根节点，左右孩子节点中比较出最大的那个，如果最大的那个节点是孩子节点，则将根节点与孩子节点进行交换，假设根节点小标为u，则左孩子节点下标为2u,右孩子节点下标为2u + 1,假设节点数为my_size，则代码如下：
void down(int u){
//定义一个变量t来表示最大值下标
int t = u;
//如果父亲有左孩子，并且左孩子为最小值。
if(2 * u > m;
MySize = n;
for(int i = 1; i > h[i];
}
//从n / 2，即最后一个孩子的父亲开始调。
for(int i = n / 2; i ; i--){
down(i);
}
while(m--){
cout
