堆简介

堆是一棵完全二叉树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。

每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆。STL 中的 priority_queue 其实就是一个大根堆。

（小根）堆主要支持的操作有：插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。

用数组模拟小根堆

小根堆的特点：每个点都小于等于左右儿子，因此堆顶是最小值。

存储：
堆顶:1
x的左儿子：2x，右儿子：2x+1.

两个核心操作:
up(x)和down(x).
其中，down(u)使h[u]处的点往下沉到形成堆，up(u)使u处的点往上走至形成堆为止。

以上的操作组合可以完成下列操作：
(1)插入一个数：heap[++cnt]=x;up(cnt);
(2)求集合中的最小值：heap[1]
(3)删除最小值:heap[1]=heap[cnt];down(1);cnt--;
(4)删除任意元素：heap[k]=heap[cnt];cnt--;down(k);up(k);
(5)修改任意元素：heap[k]=x;up(k);down(k);

代码模板

朴素版堆

//down(x)
void down(int u){
    int t=u;
    if(2*u<=cnt&&h[2*u]<h[t]) t=2*u;
    if(2*u+1<=cnt&&h[2*u+1]<h[t]) t=2*u+1;
    if(u!=t){
        swap(h[u],h[t]);
        down(t);
    }
}
//up(x)
void up(int u){
    while(u/2&&h[u/2]>h[u]){
        swap(h[u],h[u/2]);
        u=u>>1;
    }
}
//o(n)建堆
 for(int i=n/2;i;i--) down(i);

带映射版

int h[N],ph[N],hp[N],cnt;
//hp[],ph[]存储的是映射关系
//带映射版swap
void heap_swap(int u,int t){
    swap(ph[hp[u]],ph[hp[t]]);
    swap(hp[u],hp[t]);
    swap(h[u],h[t]);
}
//down(x)
void down(int u){
    int t=u;
    if(2*u<=cnt&&h[2*u]<h[t]) t=2*u;
    if(2*u+1<=cnt&&h[2*u+1]<h[t]) t=2*u+1;
    if(u!=t){
        heap_swap(u,t);
        down(t);
    }
}
//up(x)
void up(int u){
    while(u/2&&h[u/2]>h[u]){
        heap_swap(u,u/2);
        u=u>>1;
    }
}