//映射二分堆
//可插入,獲取并刪除任意元素,復(fù)雜度均O(logn)
//插入時(shí)提供一個(gè)索引值,刪除時(shí)按該索引刪除,獲取并刪除最小元素時(shí)一起獲得該索引
//索引值范圍0..MAXN-1,不能重復(fù),不負(fù)責(zé)維護(hù)索引的唯一性,不在此返回請(qǐng)另外映射
//主要用于圖論算法,該索引值可以是節(jié)點(diǎn)的下標(biāo)
//可更改元素類型,修改比較符號(hào)或換成比較函數(shù)
#define MAXN 10000
#define _cp(a,b) ((a)<(b))
typedef int elem_t;

struct heap{
	elem_t h[MAXN];
	int ind[MAXN],map[MAXN],n,p,c;
	void init(){n=0;}
	void ins(int i,elem_t e){
		for (p=++n;p>1&&_cp(e,h[p>>1]);h[map[ind[p]=ind[p>>1]]=p]=h[p>>1],p>>=1);
		h[map[ind[p]=i]=p]=e;
	}
	int del(int i,elem_t& e){
		i=map[i];if (i<1||i>n) return 0;
		for (e=h[p=i];p>1;h[map[ind[p]=ind[p>>1]]=p]=h[p>>1],p>>=1);
		for (c=2;c<n&&_cp(h[c+=(c<n-1&&_cp(h[c+1],h[c]))],h[n]);h[map[ind[p]=ind[c]]=p]=h[c],p=c,c<<=1);
		h[map[ind[p]=ind[n]]=p]=h[n];n--;return 1;
	}
	int delmin(int& i,elem_t& e){
		if (n<1) return 0;i=ind[1];
		for (e=h[p=1],c=2;c<n&&_cp(h[c+=(c<n-1&&_cp(h[c+1],h[c]))],h[n]);h[map[ind[p]=ind[c]]=p]=h[c],p=c,c<<=1);
		h[map[ind[p]=ind[n]]=p]=h[n];n--;return 1;
	}
};