heap.cpp

计算机算法设计与分析(王晓东)教材上相关源程序代码。 包括分治法(4)

//heap的成员函数实现
#include"heap.h"

template<class T>
MinHeap<T>::MinHeap(int ms):defaultSize(100){
	 maxSize = ms > defaultSize ? ms : defaultSize;
	heap = new T[maxSize];
	currentSize = 0;
}

template<class T>
MinHeap<T>::MinHeap(T a[],int n):defaultSize(100)
{
	//用一个数组来初始化堆
	maxSize = n > defaultSize ? n : defaultSize;
	heap = new T[maxSize];
	currentSize = n;
	for(int i = 0; i < n; i++)
		heap[i] = a[i];
	int curPos = (currentSize - 2) / 2;
	
	while(curPos >= 0){
		FilterDown(curPos,currentSize - 1);
		curPos--;
	}
}


template<class T>
MinHeap<T>::~MinHeap(){
 delete []heap;
}


template<class T>
void MinHeap<T>::FilterDown(const int start,const int endOfHeap){
	//自顶向下进行调整，将start节点放至对应的位置
	int i = start,j = i * 2 + 1;//start的左子树
	T temp = heap[i];
 
	while(j <= endOfHeap){
		if(j < endOfHeap && heap[j] > heap[j+1]) j++;//如果左右子树都存在，找出最小者，用j标记      
		if(temp < heap[j]) break;//找到了相应的位置
		else{
			heap[i] = heap[j];
			i = j;
			j = 2 * i + 1;
			}

	}
	
	heap[i] = temp;
}


template<class T>
void MinHeap<T>::FilterUp(const int start){
	//自底向上进行调整，将start节点放至对应的位置
 int i = start, j = ( i - 1 ) / 2;//父节点的编号
 T temp = heap[i];
 while(i > 0){
   if(temp >= heap[j]) break;//找到了相应的位置
   else{
    heap[i] = heap[j];
    i = j;
    j = (i - 1) / 2;
   }
 }
 heap[i] = temp;
}


template<class T>
bool MinHeap<T>::DeleteMin(T &x){
 if(IsEmpty()){
  cerr<<"Heap empty!"<<endl;
  return false;
 }
 x = heap[0];
 heap[0] = heap[currentSize - 1];
 currentSize--;
 FilterDown(0,currentSize-1);
 return true;
}



template<class T>
bool MinHeap<T>::Insert(const T& x){
 if(IsFull()) {
  cerr<<"Heap Full!"<<endl;
        return false;
 }
 heap[currentSize] = x;
 FilterUp(currentSize);
 currentSize++;
 return true;
}



template<class T>
bool MinHeap<T>::IsEmpty(){
  return currentSize == 0;
}


 
template<class T>
bool MinHeap<T>::IsFull(){
  return currentSize == maxSize;
}



template<class T>
void MinHeap<T>::MakeEmpty(){
 currentSize = 0
}