堆-神奇的优先队列

摘自《阿哈！算法》

一.堆的概念

堆是一种特殊的完全二叉树，就像下面这棵树一样。

我们发现这棵二叉树有一个特点，那就是所有的父结点都比子结点小。符合这样特点的完全二叉树我们称之为最小堆。

反之，所有父结点都比子结点大的完全二叉树我们称之为最大堆。

二.应用

假如有14个数，分别是99，5，36，7，22，17，46，12，2，19，25，28，1和92，请找出这14个数中最小的数。

首先我们把这14个最小的数照最小堆的要求(所有父结点都比子结点小)放入一棵完全二叉树，就像下面这棵树一样。

很显然最小的数就在堆顶，假设存储这个堆的数组叫做heap的话，最小数就是heap[1]。如果此时我们将堆顶的数删除，新加入一个数23放到堆顶，要重新找到最小的数，该怎么调整呢？

向下调整！我们需要就这个数与它的两个儿子2和5比较，选择一个较小的与它交换。若交换后还不满足最小堆的特性，那么继续向下调整，直到符合最小堆的特性为止。

                                         

综上所述，当新增一个数被放到堆顶时，如果此时不符合最小堆的特性，则需将这个数向下调整，直到找到合适位置为止。

说了这么多，那么如何建立一个堆呢？一种比较快的方法是直接将这14个数放入一个完全二叉树中(这里我们还是用一个一维数组来存储二叉树)

                       

在这棵完全二叉树中，我们从最后一个结点开始，依次判断以这个结点为根的子树是否符合最小堆的特性。如果所有子数都符合的话，那么整棵树就是最小堆了。

因为所有叶结点都没有儿子，因此所有叶结点都不用处理。直接从第n/2个结点开始处理这个完全二叉树。

注意完全二叉树有一个性质:最后一个非叶结点是第n/2个结点，它的左儿子是结点2*(n/2),右儿子是2*(n/2)+1，由二叉树图可以看出。

小结这个创建堆的算法:

把n个元素建立一个堆，首先我们可以将这个n个结点以自顶向下、从左到右、的方式从1到n编码。这样就可以把这n个结点转换成一棵完全二叉树。紧接着从最后一个非叶结点(编号为n/2)开始到根节点(编号为1)，逐个扫描所有的结点，根据需要将当前结点向下调整，直到以当前结点为根结点的子树符合堆的特性。

代码实现其实就是堆排序:

#include<bits/stdc++.h>
using namespace std;
int heap[105]; //用来存放堆的数组
int n; //用来存储堆中元素的个数，也就是堆的大小
//向下调整函数
void siftdowm(int i) //传入一个需要向下调整的节点编号i,这里传入1，即从堆的顶点开始向下调整
{
    int it,flag=0; //flag用来标记是否需要继续向下调整
    //当i结点有儿子(其实至少有左儿子)并且有需要继续调整的时侯循环就执行
    while(i*2<=n&&flag==0)
    {
        //首先判断它和左儿子的关系,并用it记录较小的结点编号
        if(heap[i]>heap[i*2])
            it=i*2;
        else
            it=i;
        //如果它有右儿子，再对右儿子进行讨论
        if(i*2+1<=n)
        {
            //如果右儿子的值更小，更新较小的结点编号
            if(heap[it]>heap[i*2+1])
                it=i*2+1;
        }
        //如果发现最小的结点编号不是自己，说明子节点中有比父节点更小的
        if(it!=i)
        {
           swap(heap[it],heap[i]); //交换它们
           i=it; //更新i为刚才与它交换的子节点编号，便于接下来继续向下调整
        }
        else
            flag=1; //否则说明当前的父节点已经比两个子节点都要小了，不需要再进行调整
    }
}
//建立堆的函数
void creat()
{
    int i;
    //从最后一个非叶节点到第1个节点依次向上调整
    for(i=n/2;i>=1;i--)
        siftdowm(i);
}
//删除最大的元素
int deletemax()
{
    int temp;
    temp=heap[1]; //用一个临时变量记录堆顶点的值
    heap[1]=heap[n]; //将堆的最后一个点赋值d到堆顶
    n--;
    siftdowm(1); //向下调整
    return temp;
}
int main()
{
    int i,num;
    //读入需要排序的数字个数
    scanf("%d",&num);
    for(i=1;i<=num;i++)
        scanf("%d",&heap[i]);
    n=num;
    //建堆
    creat();
    //删除顶部元素，连续删除n次，其实也就是从小到大把数输出来
    for(i=1;i<=num;i++)
        printf("%d ",deletemax());
    return 0;
}