堆-优先队列

前置知识：二叉树。

参考资料

暂无

---

堆就是优先队列，可以用来解决动态区间查询最值问题。

堆就是一个完全二叉树，可以插入节点，删除根节点（也可以删除特定节点）。

为了方便，普通的堆节点 \(i\) 的父亲就是 \([i\div2]\) （\([x]\) 表示不超过 \(x\) 的最大整数）。

节点 \(i\) 的左儿子是 \(i\times2\)，右儿子是 \(i\times2+1\)。

对于一个大顶堆：

每次插入节点的时候，就把节点插在完全二叉树的最后，如果它比它的父亲节点大，就把它和父亲交换，然后一直和父亲比较交换，直到父亲的值比它大，或者它已经成为树根。

每次删除根节点的时候，就把完全二叉树最后的那个节点放到根节点上，然后让最后那个节点原来的位置消失。然后把单前的根节点，跟它的左儿子比较，如果比左儿子小，就跟左儿子交换，然后不停跟左儿子比较交换知道它比左儿子大或着他没有左儿子。

时间复杂度 \(O(n\log n)\)。

如果你掌握了这些，那蒟蒻就放代码了：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
class heap{
public:
    int v[N],sz;
    heap(){sz=0;}
    void push(int x){ //插入
        int p=++sz;
        for(v[p]=x;p>1&&v[p>>1]<v[p];p>>=1)
            swap(v[p>>1],v[p]);
    }
    void pop(){ //删除顶
        swap(v[1],v[sz--]);
        for(int p=1;(p<<1)<=sz&&v[p<<1]>v[p];p<<=1)
            swap(v[p<<1],v[p]);
    }
    int top(){return v[1];}
}q;
int main(){
    int f,x;
    while(scanf("%d",&f)==1){
        if(f==1) scanf("%d",&x),q.push(x);
        else if(f==2) q.pop();
        else if(f==3) printf("%d\n",q.top());
    }
    return 0;
}

可是很多时候我们急需一个堆，那就不需要写那么长，C++库里自带了数据结构堆：

priority_queue<int> q;

默认是大顶堆，支持 \(q.push(x)\)、\(q.pop()\)、\(q.top()\)。如果想要小顶堆，只需这么写：

priority_queue<int,vector<int>,greater<int>> q;

如果你要自定义比较运算符 \(cmp\)，可以这么写：

class cmp{  //自定义比较运算符cmp
public:
    bool operator()(int x,int y){
        return abs(x-5)>abs(y-5); //最接近5的数为堆顶
    }
};
priority_queue<int,vector<int>,cmp> q;

与 \(sort()\) 不一样，堆顶与堆中每个元素 \(cmp\) 都是 \(0\)。比如你的 \(cmp\) 内是 \(return~x>y;\) 那么就是小顶堆。

特别模块：双堆删除

如果你想删除堆中特定的一个数，那么就要用到双堆删除。

开另一个堆，把要删的数 \(push\) 进去。每次取原堆 \(top()\) 的时候，如果原堆 \(top()\) 等于这个堆的 \(top()\)，就 \(pop()\)，直到这个堆没数了或者两个堆堆顶不相同了。

class double_heap{
public:
    priority_queue<int> que,del;
    void push(int x){que.push(x);}
    void delet(int x){del.push(x);}
    int top(){
        while(del.size()&&que.top()==del.top())
            del.pop(),que.pop();
        if(que.empty()) return -1;
        return que.top();
    }
}q;

关于堆的还有左偏树-可并堆，但这里不讲，那是后续知识。

祝大家学习愉快！