1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

//heap
template<typename T,bool comp(const T& a,const T& b)>
struct HEAP
{
	T ary[maxnode];
	int f;
	HEAP(){f=0;}
	bool empty(){return f==0;}
	void push(const T& w)
	{
		ary[++f]=w;
		for(int k=f;k!=1&&comp(ary[k],ary[k/2]);k/=2)
		{
			Swap(ary[k],ary[k/2]);
		}
	}
	T top(){return ary[1];}
	T pop()
	{
		T tmp=ary[1];
		ary[1]=ary[f--];
		for(int k=1,son=k*2;son<=f;k=son,son=k*2)
		{
			if(son+1<=f&&comp(ary[son+1],ary[son]))
				++son;
			if(comp(ary[son],ary[k]))
				Swap(ary[k],ary[son]);
			else break;
		}
		return tmp;
	}
};