如何手写一个堆

下标从1开始，如果从0开始的话，他的左儿子的下标就等于0*2 = 0，麻烦

手写堆可以实现的操作：1，插入一个数  2，求集合当中的最小值  3，删除最小值

4，删除任意一个元素  5，修改任意一个元素（stl中的堆不能直接实现功能四五，可以间接实现）

 堆是一颗完全二叉树

 以小根堆为例，根结点小于等于他的子节点，所以小根堆的根节点是最小的值

堆用一个一维数组存储，图中的x指下标

 刚开始输入所有值之后维护这棵树，让他成为堆的方法

 从倒数第二层开始往下down，倒数第二层的down执行一次，倒数第三层执行两次.....

总共的时间复杂度算下来是O(n)

堆的基本操作：

down（），up（），上面的五种操作全部可以用这两个拼接出来

down就是在父亲结点比儿子节点大了，然后在两个儿子结点中找一个最小的，然后和他交换，直到不再需要交换为止

up操作中小的子节点只需要和父节点进行比较然后交换 

堆排序

#include
#include
#include
#include
#includeusing namespace std;const int N = 100010;int m, n;
int h[N], siz;void down(int u)
{int t = u;if (u * 2 <= siz && h[u * 2] < h[u]) t = u * 2;if (u * 2 + 1 <= siz && h[t] > h[u * 2 + 1]) t = u * 2 + 1;if (t != u){swap(h[t], h[u]);down(t);}
}int main()
{cin >> n >> m;for (int i = 1; i <= n; i++) cin >> h[i];siz = n;for (int i = n / 2; i >= 1; i--) down(i);while (m--){cout << h[1] << ' ';h[1] = h[siz];siz--;down(1);}return 0;
}

 这里要把与siz的比较放在前面，否则会出现segmentation fault的错误

模拟堆

 hp数组是用数的下标得到插入顺序

ph数组是根据插入顺序得到数的下标

在交换两个数的时候需要先交换idx指向堆的关系，接着交换堆指向idx的关系，最后在将值进行交换

#include
#include
#includeusing namespace std;const int N = 100010;int n;
int h[N],hp[N],ph[N],cnt;//如果要删除的是第k个数，那么直接交换就可以了，但是插入的是第k个插入的数，所以就需要idx来记录插入的顺序
//因为有idx来记录，所以idx和点之间就会存在联系，但是无法通过值来查找对应的idx，所以在原来ph【】数组的基础上，需要引进hp【】数组
//从而通过hp【i】 =  idx （i表示在数组中的第i位，idx表示在第idx次插入的数），有了hp【】数组的表示，
//那么我们就可以通过ph【】来找到第idx位插入的数字在第数组的第i位。
//所以在执行交换操作是的时候，我们要先交换idx指向堆的关系，接着交换堆指向idx的关系，最后在将值进行交换
void heap_swap(int a,int b)
{swap(ph[hp[a]],ph[hp[b]]);swap(hp[a],hp[b]);swap(h[a],h[b]);
}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);}
}void up(int u)
{while(u / 2 && h[u] < h[u / 2]){heap_swap(u,u / 2);u >>= 1;}
}int main()
{cin>>n;int idx = 0;while(n -- ){char op[5];int k , x;cin>>op;if(!strcmp(op,"I")){cin>>x;cnt ++;idx ++;ph[idx] = cnt;hp[cnt] = idx;h[cnt] = x;up(cnt);}else if(!strcmp(op,"PM")) cout<>k;k = ph[k];heap_swap(k,cnt);cnt --;up(k),down(k);}else{cin>>k>>x;k = ph[k];h[k] = x;up(k),down(k);}}return 0;
}