堆

堆是一种特殊的完全二叉树。 他满足下列性质： ``` 对于每个节点都有一个值，而且它的值小于等于父节点的值。 ``` 也就是说，根节点的值最大。 堆支持插入和删除操作，即插入一个新的值和删除堆顶（根节点）的值。而且操作完成后还要满足堆的性质。 由于完全二叉树的特殊性质，所有节点都排列的非常密集。所以我们用一种特殊的方法记录一棵完全二叉树： 根节点编号为1。 对于编号为x的节点，他的左子节点编号为2\*x，右子节点编号为2\*x+1，父节点编号为x/2。 那么我们就能用一个数组记录下一棵完全二叉树。 ```cpp int cnt;//表示树的节点个数 int tr[100];//记录每个节点的值 void push(int x){//插入值为x的节点 tr[++cnt]=x;//在二叉树的最后加上新来的节点 int now=cnt;//从当前节点开始往上走，维护堆的性质 while(now>1){//若已经走到根节点了，那么停止 if(tr[now]>tr[now/2]){//若当前节点的值大于父节点的值，那么要交换 swap(tr[now],tr[now/2]); now/=2;//继续往上走 } else break;//已经满足堆的性质，退出循环 } } void pop(){//删除根节点 tr[1]=tr[cnt--];//节点数减1，把最后一个节点移到根节点上 int now=1;//从根节点往下走，维护堆的性质 while(now*2<=n){//若没有子节点了，那么停止 int mx; if(now*2+1>n||tr[now*2]>tr[now*2+1])//求出哪边的子节点更大 mx=now*2; else mx=now*2+1; if(tr[mx]>tr[now]){//若子节点的值比当前节点大，那么交换 swap(tr[mx],tr[now]); now=mx; } else break;//已经满足堆的性质，退出循环 } } ``` 插入和删除的时间复杂度都是O(log n)的。 在STL里有priority_queue（优先队列），有着跟堆一样的功能。 ```cpp priority_queue<int> q;//定义 q.push(x);//加入一个新的元素 q.pop();//删除堆顶元素 q.top();//查看堆顶元素的值 q.size();//查看堆的大小 q.empty();//判断堆是否为空 若要使用小根堆（即每个节点的值都大于等于父节点，根节点值最小），那么可以将定义改成： priority_queue<int,vector<int>,greater<int> >q; 若要对结构体进行按自定义的顺序进行排序，那么就要重载结构体的小于号。 struct node{ int x,y; //x小的为父节点，若x相等，那么y小的为父节点 bool operator<(node b)const{ if(x!=b.x)return x>b.x; return y>b.y; } }; priority_queue<node> q; ```