www.pudn.com > XiaoYuanDaoYouTu.rar > minheap.h

//自定义的swap函数 
template 
swap(Elem A[],int x,int y) 
{ 
	Elem temp=A[x]; 
	A[x]=A[y]; 
	A[y]=temp; 
} 
 
//最小堆 
template  
class minheap 
{ 
private: 
	Elem *Heap;                         //堆指针 
	int size;						    //堆大小 
	int n;								//堆中实际元素个数 
 
public:	 
	//构造函数，以一个已有的数组为依据	 
	minheap(Elem *A,int num,int max)     
	{ 
		Heap=A;                     //指向已有数组 
		n=num; 
		size=max; 
		buildHeap(); 
	} 
 
	bool isempty() const 
	{ 
		return n<=0; 
	} 
 
	bool isLeaf(int pos)            //判断是否为叶 
	{ 
		return (pos>=n/2)&&(pos=0;i--) 
			siftdown(i); 
	} 
	//该函数将每一个元素放入其在堆中的合适位置 
	void siftdown(int pos) 
	{ 
		while(!isLeaf(pos)) 
		{ 
			int j=leftchild(pos); 
			int rc=rightchild(pos); 
			if((rcHeap[rc].m_nWeight))    //取较小的儿子 
				j=rc; 
			if(!(Heap[pos].m_nWeight>Heap[j].m_nWeight)) return;  //结束 
			//比小儿子大，和小儿子交换 
			swap(Heap,pos,j); 
			pos=j; 
		} 
	} 
	bool insert(Edge &val) 
	{ 
		if(n>=size) return false; 
		int curr=n++;               //先将插入的元素放到堆的末尾 
		Heap[curr] = val; 
		//这其实是一个siftup的过程 
		while((curr!=0) && (Heap[curr].m_nWeight < Heap[parent(curr)].m_nWeight)) 
		{ 
			swap(Heap,curr,parent(curr)); 
			curr=parent(curr); 
		} 
		return true; 
	} 
	Elem removemin()               //取最小元素 
	{ 
		swap(Heap,0,--n);          //先将最小元素放到堆的末尾 
		if(n!=0) siftdown(0);      //重建堆 
		return Heap[n]; 
	} 
	//取任何一个元素，比上面的函数多一个siftup的过程，注意siftup和siftdown两个过程只执行其中的一个 
	bool remove(int pos,Elem &it)   
	{ 
		if((pos<0)||(pos>=n)) return false; 
		swap(Heap,pos,--n); 
		while(pos!=0&&(Heap[pos]