STL 堆

测试题目：洛谷P3378 【模板】堆

插入，删除，取最小

---

方法0：STL 优先队列

1198ms

#include<iostream>

#include<cstdio>

#include<queue>

#include<vector>

using namespace std;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,op;

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

int main(){

    //freopen("in.txt","r",stdin);

    n=read();

    for(int i=;i<=n;i++){

        op=read();

        if(op==) q.push(read());

        else if(op==) printf("%d\n",q.top());

        else q.pop();

    }

}

---

方法1：algorithm库 heap系列函数

520ms 这个数字.....

make_heap(begin,end,cmp) 建堆 前闭后开    cmp定义<运算，可选 注意同样是默认大根堆

push_heap(begin,end,cmp) 插入 前闭后开 插入最后一个元素

pop_heap(begin,end,cmp) 删除 把堆顶元素放到最后一个位置

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long ll;

const int N=1e6+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,op,x;

int a[N],len=;

inline bool cmp(int a,int b){return a>b;}

int main(){

    n=read();

    for(int i=;i<=n;i++){

        op=read();

        if(op==){

            a[++len]=read();

            push_heap(a+,a++len,cmp);

        }else if(op==) printf("%d\n",a[]);

        else pop_heap(a+,a++len,cmp),len--;

    }

}

---

方法2：pb_ds库

据说竞赛可用

#include <ext/pb_ds/priority_queue.hpp>

using namespace __gnu_pbds;

使用方法：__gnu_pbds::priority_queue<int,greater<int>,pairing_heap_tag> q; 第三个参数换成想用的名称就行了，默认配对堆

支持join操作，然而本文不考虑

pairing_heap_tag 428ms

binomial_heap 544ms

rc_binomial_heap 610ms

thin_heap_tag 790ms

结合WC课件中的测试，用默认的pairing就好了

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <ext/pb_ds/priority_queue.hpp>

using namespace std;

using namespace __gnu_pbds;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,op,x;

__gnu_pbds::priority_queue<int,greater<int> > q;

int main(){

    n=read();

    for(int i=;i<=n;i++){

        op=read();

        if(op==) q.push(read());

        else if(op==) printf("%d\n",q.top());

        else q.pop();

    }

}