heap

最小优先：priority_queue<int,vector<int>,greater<int> >Q_minfirst;
最大优先：priority_queue<int,vector<int>,less<int> >Q_maxfirst;

题目链接:小根堆

template<class T>
struct heap
{
    T hp[1000005];
    int idx;
    heap():idx(0)
    {
        memset(hp,0,sizeof(hp));
    }
    void push(T x)
    {
        hp[++idx]=x;
        int t=idx;
        while(t!=1 && hp[t]<hp[t>>1])
            swap(hp[t>>1],hp[t]),t>>=1;
    }
    void pop(void)
    {
        hp[1]=hp[idx--];
        int t=1,y=1;
        while(1)
        {
            if((t<<1)<=idx && hp[t<<1]<hp[y])
                y=t<<1;
            if((t<<1|1)<=idx && hp[t<<1|1]<hp[y])
                y=t<<1|1;
            if(t==y)return;
            swap(hp[t],hp[y]),t=y;
        }
    }
    T top(void)
    {
        return hp[1];
    }
};