minheap.h

队放置于硬盘上的文件进行外排序

/********** less template **********/
//x小于y，返回TRUE，否则返回FALSE
template <class Elem>
bool less(Elem x, Elem y)
{
	return(x < y);
}


/*********** swap template***********/
template <class Elem>
void swap(Elem * BUFarray, int i, int j)
{
	Elem temp;
	temp = BUFarray[i];
	BUFarray[i] = BUFarray[j];
	BUFarray[j] = temp;
}



/************** 最小值堆template ***************/
template <class T>class MinHeap{
	public:

		int MaxSize;	//heapArray MEMORY1 MaxSize
		int CurrenSize;	//current number of elements in the heapArray
			
	public:
		T * heapArray;	//pointer to the heapArray array		
		//constructor
		MinHeap(T * h, int num, int MEMORY1){
			heapArray = h;
			CurrenSize = num;
			MaxSize = MEMORY1;
			BuildHeap();
			}

		//set the MaxSize of heapArray
		void setSize(int x){
			CurrenSize = x;
		}
		
		//put an elment in its correct place
		void SiftDown(int pos){
			while(!isLeaf(pos)){

				//get children
				int j = leftchild(pos);
				int rc = rightchild(pos);

				if((rc < CurrenSize) && (less(heapArray[rc], heapArray[j])))	//j is the less child
					j = rc;
				if(less(heapArray[pos], heapArray[j]))
					return;
				swap(heapArray, pos, j);
				pos = j;
				if(pos>=CurrenSize)
					break;
 			}
		}

		//MaxSize
		int heapsize() const{
			return CurrenSize;
		}

		//judge a leaf
		bool isLeaf(int pos) const{
			return (pos >= CurrenSize/2)&&(pos < CurrenSize);
		}

		//left child
		int leftchild(int pos) const{
			return 2*pos+1;
		}

		//right child
		int rightchild(int pos) const {
			return 2*pos+2;
		}

		//parent
		int parent(int pos) const{
			return (pos-1)/2;
		}

		T getmin(){
			return heapArray[0];
		}
		
		//minValue
		bool removemin(T & it){
			if(CurrenSize == 0)
				return false;
			
			//swap min with the last element
			swap(heapArray, 0, --CurrenSize);

			//shif down new root
			if(CurrenSize != 0)
				SiftDown(0);
			
			//return deleted value
			it = heapArray[CurrenSize];
			return true;

		}

		//bulid heapArray
		void BuildHeap(){
			for(int i = CurrenSize/2-1; i >= 0; i--)
				SiftDown(i);
		}

};