一：定义以及部分性质
1：堆中某个节点的值总是不大于或不小于其父节点的值；
2：堆总是一棵完全二叉树。
3：最后一个非叶结点是第n/2个结点。这里建堆的时候会用到，复杂度可以降到O(n)；
二：关于建堆
如果一个点为u，那么它的左儿子为2*u，右儿子为2*u+1
对于小根堆来讲，每个以u为根节点的树，它的左右儿子的值一定大于父节点。
所以对堆进行建立的时候，如果当前点与它的左右儿子并不满足这一性质，就需要进行交换。
对于建堆的过程：
由(一)第三条，我们建堆的时候，只需要从n/2开始，到1即可。因为已知最后一个非叶结点是n/2，那么>n/2的结点，都是叶子结点，它本身所构成的子树只有它本身。一定符合小根堆性质，所以是没必要看的。我们从第n/2结点开始，每次让它向下比较一次，变为局部的合法(比如第一次只有三个点，满足父节点都小于左右儿子结点)。然后它的向上的父节点再向下比较，那么每次比较，都会得到一个局部合法的子树(本次进行的父节点往下的子树)。所有的n/2~1都这么操作，一定可以把整个完全二叉树变成合法的小根堆。
有：
for(int i=n/2;i>=1;i--) { down(i); }
对于向下比较的过程，我们定为down(u)函数。由小根堆的性质，u为父节点，那么它的左右儿子h[2*u]和h[2*u+1]都要大于它，否则就要进行交换：
void down(int u) { //t表示三个点中的最小值 int t=u; //判断是否有左儿子 if(u*2<=siz&&h[2*u]<h[t]) { t=2*u; }
//是否有右儿子 if(2*u+1<=siz&&h[2*u+1]<h[t]) { t=2*u+1; } if(u!=t) {
//需要交换，则交换，继续down往下判断 swap(h[u],h[t]); down(t); } }
只要down()就可以把堆给建好了。
关于up操作：
比down更简单，只需要与它的父节点u/2进行比较即可，非法即交换。
void up(int u) { while(u/2>=1&&h[u/2]>h[u]) { swap(u,u/2); u=u/2; } }
三：堆的操作
定siz为树大小
1：插入一个数：
直接在末尾加一个，所以++size处插入新数，然后进行更新树。由于此时它处于树的最底部，所以直接up(size)即可。
2：求集合中最小值：
h[1]
3：删除最小值：
把树尾覆盖上去，siz--，由于此时它处于树的顶部，所以直接down(1)即可。
4：删除任意一个元素：
删除K号结点。与3类似，直接把树尾覆盖上去，siz--，但是需要up(k)或down(k)一遍，为了简便，把up和down都写上，只会执行其中一个。
5：修改任意一个元素
直接修改h[k]=x，up(k),down(k)
四：堆排序
堆的其中一个作用，堆排序：时间复杂度O(NlogN)
板子题：https://www.acwing.com/problem/content/description/840/
#include<cstdio> #include<cstring> #include<vector> #include<set> #include<algorithm> #include<iostream> #include<vector> using namespace std; typedef long long ll; const int maxn=1e5+10,maxn2=31*maxn; int n,m; int h[maxn],siz;//1~n void down(int u) { //t表示三个点中的最小值 int t=u; //判断是否有左儿子 if(u*2<=siz&&h[2*u]<h[t]) { t=2*u; } if(2*u+1<=siz&&h[2*u+1]<h[t]) { t=2*u+1; } if(u!=t) { swap(h[u],h[t]); 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; }
vector排序版：
#include<cstdio> #include<cstring> #include<vector> #include<set> #include<algorithm> #include<iostream> #include<vector> using namespace std; typedef long long ll; const int maxn=2e5+10,maxn2=31*maxn; const int inf=1e18+10; ll a[maxn],b[maxn]; int main() { int n,m; vector<int>v; cin>>n>>m; int x; for(int i=1;i<=n;i++) { cin>>x; v.push_back(x); } sort(v.begin(),v.end()); for(int i=0;i<m;i++) cout<<v[i]<<" "; cout<<endl; return 0; }
五：堆操作的基本实现：