堆是一种特殊的完全二叉树，是树的一种常见的应用，最简单的便是解决将无序的数列从大到小排列或者从小到大排列。性能极佳。

    堆分两种，一种是最大堆，即所有的父节点都大于它的两个子节点。另一种是最小堆，即所有的父节点都小于它的两个子节点。

    如果一组数列，是无序的，要将它有序的排列，那么：

min = 9999;

for(i=0; i<n; i++){

    if(num[i] < min){

        min = num[i];

    }

}

    这是最简单也是最高效的算法。可是，如果现在要删除最小数，在数列中插入一个任意一个数，此时再求最小值呢？那么就要重复上面的操作。那么问题来了，如果这个动作要重复100亿次呢？此时，时间复杂度就要100亿×数列的长度。即O(num.count*100亿)。这是不科学的，这个时候，我们引入了堆。

    最小堆的根节点永远是最小值！此时我们删掉了最小值，也就是根节点，在根节点的位置插入一个任意值，这个时候这个树就不是堆了，我们要把根节点向下移动，找到他合适的位置，也就是他要比他父节点大，比他的根节点小。此时这个树又恢复成了堆。

    现在有如下堆：

    堆的黑色数组表示节点的编号，在圈圈里。红色数组表示这个节点的值。我们现在要从小到大排列一个数列。也就是对红色数组进行排序。

    1、1号节点是根节点，永远是最小值，这是最小堆的特性。反之最大堆的根节点是最大值。

    2、将1号节点的值改变为新插入的任意值。

    3、将新插入的值向下移动，使树恢复为最小堆。和它的左子节点还有右子节点比较，若大，则交换位置。如此反复，直到不能再交换位置了。

    使用最小堆来从小到大排列一个无序数列的全部代码如下，时间复杂度为O(NLogN)：

#include <stdio.h>

//存放堆

int h[100];

//存储堆的元素个数

int n;

//交换元素

void swap(int x, int y){

    int t;

    t = h[x];

    h[x] = h[y];

    h[y] = t;

}

//向下调整

void siftdown(int i){

    int t, flag=0;

    //判断该点的做儿子是否存在

    while(i*2 <= n && flag == 0){

        //如果左儿子存在，则判断是否交换值

        if(h[i] > h[i*2])

            t = i * 2;

        else

            t = i;

        //右儿子是否存在

        if(i*2+1 <= n && h[t] > h[i*2+1]){

            t = i*2+1;

        }

        //如果需要交换则交换

        if( t!= i){

            swap(t, i);

            i = t;

        //如果不需要交换，则准备退出while

        }else{

            flag = 1;

        }

    }

}

//向上调整，本函数本次将不会用到。

void siftup(int i){

    int flag = 0;

    while(i != 1 && flag == 0){

        if(h[i] < h[i/2]){

            swap(i, i/2);

            i = i/2;

        }else{

            flag = 1;

        }

    }

}

//创建堆

void create(){

    int i;

    for(i=n/2; i>=1; i--){

        siftdown(i);

    }

}

//获取最小的元素

int getMin(){

    int t;

    //堆顶（根节点）为最小值

    t = h[1];

    //删除根节点，把堆的最后一个元素赋给根节点

    h[1] = h[n];

    n--;

    //把根节点向下移动，使堆恢复最小堆

    siftdown(1);

    return t;

}

int main(){

    int i, num;

    scanf("%d", &num);

    for(i=1; i<=num; i++){

        scanf("%d", &h[i]);

    }

    n = num;

    //创建堆

    create();

    //讲堆从小到大排列

    for(i=1; i<=num; i++){

        printf("%d ", getMin());

    }

    return 0;

}

输入：

14

99 5 36 7 22 17 46 12 2 19 25 28 1 92

//输出：

1 2 5 7 12 17 19 22 25 28 36 46 92 99

    若使用最大堆，根节点就是整个数列的最大值，那么将h[1]和h[n]交换位置，此时h[n]就是最大值，然后将h[1]向下移动已恢复新的堆。此时将堆的大小减一，重复上面的操作。时间复杂度将会从O(NLogN)降低到O(NLogK)

    完整代码如下：

#include <stdio.h>

//存放堆

int h[100];

//存储堆的元素个数

int n;

//交换元素

void swap(int x, int y){

    int t;

    t = h[x];

    h[x] = h[y];

    h[y] = t;

}

//向下调整

void siftdown(int i){

    int t, flag=0;

    //判断该点的做儿子是否存在

    while(i*2 <= n && flag == 0){

        //如果左儿子存在，则判断是否交换值

        if(h[i] < h[i*2])

            t = i * 2;

        else

            t = i;

        //右儿子是否存在

        if(i*2+1 <= n && h[t] < h[i*2+1]){

            t = i*2+1;

        }

        //如果需要交换则交换

        if( t!= i){

            swap(t, i);

            i = t;

        //如果不需要交换，则准备退出while

        }else{

            flag = 1;

        }

    }

}

//创建堆

void create(){

    int i;

    for(i=n/2; i>=1; i--){

        siftdown(i);

    }

}

//从小到大排序

int minToMaxSort(){

    while(n>1){

        swap(1, n);

        n--;

        siftdown(1);

    }

}

int main(){

    int i, num;

    scanf("%d", &num);

    for(i=1; i<=num; i++){

        scanf("%d", &h[i]);

    }

    n = num;

    //创建堆

    create();

    //排序

    minToMaxSort();

    for(i=1; i<=num; i++){

        printf("%d ", h[i]);

    }

    return 0;

}

输入：

14

99 5 36 7 22 17 46 12 2 19 25 28 1 92

//输出：

1 2 5 7 12 17 19 22 25 28 36 46 92 99

Ps:本算法参考《啊哈！算法》一书。