最小优先：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];
}
};
