存储方式：

用一位数组存储一个堆
根节点是a[x],左孩子是a[2x],右孩子是a[x+1]

基本操作：

void down(int u ){
    int t = u;
    if(u*2 <= size && h[u*2] < h[t]) t = u*2;//左孩子比根节点小
    if(u*2+1 <= size && h[u*2+1] < h[t]) t= u*2+1;//右孩子比根节点小
    if(u!=t){
        swap(h[u],h[t]);
        down(t);//继续循环
    }
    /*n/2开始即从下往上递归，可以保证子节点已经是有序了的*/
}

void up(int u){
    while(u/2 && h[u/2] > h[u]){
        swap(h[u/2],h[u]);
        u /= 2;
    }
}

手写堆：

1、插入一个数
heap[++size] =x; up(size);
2、求集合当中的最小值
heap[1];
3、删除最小值
heap[1] = heap[size]; size–; down(1);
4、删除任意一个元素
heap[k] = heap[size]; size–; down(k)/up(k);
5、修改任意一个元素
heap[k] = x;down(k)/up(k);

例题838：

#include <iostream>
const int N = 100010;

int n , m;
int h[N],size;

void down(int u ){
    int t = u;
    if(u*2 <= size && h[u*2] < h[t]) t = u*2;//左孩子比根节点小
    if(u*2+1 <= size && h[u*2+1] < h[t]) t= u*2+1;//右孩子比根节点小
    if(u!=t){
        swap(h[u],h[t]);
        down(t);//继续循环
    }
    /*n/2开始即从下往上递归，可以保证子节点已经是有序了的*/
}

int main(){
    sacnf("%d%d",&n,&m);
    for(int i = 1 ; i < n ; i++) sacnf("%d",&h[i]);//从1开始存，方便操作
    size = n;

    for(int i =  n/2; i ; i --) down(i);

    while(m--){
        printf("%d ",h[1]);
        h[1] = h[size];//输出小根堆最小值，再把尾元素换上来继续down操作
        size -- ;
        down(1);
    }
}