堆

对于stl priority_queue ，我们自己定义的类自己重载<，对于非自定义类我们默认大根堆，如若改成小根堆则写成std::priority<int,vector<int>,greator<int> >。时间复杂度除了pop push是O(log)外都是O(1)。

当然手打会比stl快不少，下面介绍手打堆。

对于手打堆他出来用于优先队列之外还能用于堆排序，就先建堆，然后依次取出。除已有操作以外，还有一个建堆过程，一般用于堆排序，就是一次把许多数的建成堆，就是先按原顺序建树，从(len>>1)（第一个不是叶子节点的点）开始向前走，对每一个点进行down()操作。其他的操作同。然而我们手打堆可以进行一些操作来使他可以删除堆中任意一点。一般删除堆中元素，有三种办法，一是打标记，二是用垃圾堆，三是手打堆直接删除。

#include 
     
      #include 
      
       #include 
       
        namespace Heap{  const int N=20010;  const int Inf=0x3f3f3f3f;  int key[N],len;  inline void Init(){    key[0]=-Inf;  }  inline bool empty(){    return len==0;  }  inline int top(){    return key[1];  }  inline void push(int val){    key[++len]=val;int now=len;    while(key[now]
        
         >1])      std::swap(key[now],key[now>>1]),now=now>>1;  }  inline void pop(){    key[1]=key[len--];int now=1;    while(now<=(len>>1)){      int next=now<<1;      if(next
         
          key[next|1])++next;      if(key[next]>=key[now])break;      std::swap(key[next],key[now]),now=next;    }  }}int n;long long ans;int main(){  scanf("%d",&n),Heap::Init();  for(int i=1,x;i<=n;++i)    scanf("%d",&x),Heap::push(x);  for(int i=1,x,y;i