堆是一棵完全二叉树,其每个节点都有一个键值,且每个节点的键值都大于等于/小于等于其父亲的键值。
每个节点的键值都大于等于其父亲键值的堆叫做小根堆,否则叫做大根堆。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; } }