heap.h

这是清华大学出版社的《数据结构》的电子文档讲义

#include <fstream.h>
#include "array.h"

template <class Type> class minHeap{							//最小堆的类声明
	public:
 		minHeap();								//构造函数
		minHeap(unsigned maxSize);								//构造函数1：建立空堆
 		minHeap(minHeap<Type>& mH);								//构造函数2
//  		~minHeap(){delete heap;}								//析构函数
  		const minHeap<Type>& operator=(const minHeap &R);		//堆复制赋值
  		int insert(Type &x);								//将x插人到最小堆中
  		int removeMin(Type &x);									//删除堆顶上的最小元素
  		int isEmpty()const{return currentSize == 0;}			//判堆空
  		int isFull()const{return currentSize == maxHeapSize ;}	//判堆满
  		void makeEmpty(){currentSize = 0;}						//置空堆
  		int currentSize ;                         	//最小堆中当前元素个数
	private:
  		//num{DefaultSize = 10};
  		//Type * heap;								//存放最小堆中元素的数组
		array<Type> heap;							//存放最小堆元素的向量
      	int maxHeapSize ;							//最小堆当前最多允许元素个数
      	void filterDown(int i, int m ) ;			//从i到m自顶向下调整为最小堆
      	void filterUp(int i );						//从i到0自底向上调整为最小堆
    	};

template<class Type>minHeap<Type>::minHeap(unsigned maxSize):heap(maxSize){
	maxHeapSize = maxSize;
	currentSize = 0;}								//调用向量构造函数,当前大小为0

//template<class Type>minHeap<Type>::minHeap(array<Type> arr){
//	maxHeapSize =  DefaultSize<n?n：DefaaltSize ;		//按参数给定堆最大体积
//    heap = new Type [ maxHeapSize ] ;	//创建堆存储空间heap[maxHeapSize]

template<class Type>minHeap<Type>::minHeap(minHeap<Type>& mH){
    heap(mH.heap);										//复制堆,
	maxHeapSize = mH.maxHeapSize;
	currentSize = mH.currentSize;						//
	} 
/* int currentPos = (currentSize-2)/2;				//找最初调整位置：最后的分支结点编号
    while ( currentPos >= 0){						//自底向上逐步扩大形成堆
    	filterDown (currentPos, currentSize-1);		//局部自上向下调整
        currentPos--;								//再向前换一个分支结点
        }
    }*/

template<class Type>
void minHeap <Type>::filterDown(const int start, const int endOfHeap){
	//私有函数：从结点start开始到EndOjHeap为止,自上向下比较,如果子女的值
	//小于双亲结点的值,则相互交换,这样将一个集合局部调整为最小堆。
	int i = start,  j = 2 * i+1; Type temp = heap[i];			//j是i的左子女位置,暂存结点i
	while(j <= endOfHeap){										//检查是否到最后位置
        if ( j<endOfHeap && heap[j].key>heap[j+1].key) j++;		//j指向子女的小者
        if ( temp.key <= heap[j].key ) break;					//小则不做调整
        else { heap[i] = heap[j];								//否则小者上移,
		i = j; 													//i下降到j的位置
		j = 2* j +1;}											//j下降到其左子位置
        }														//继续向下层比较
    heap[i] = temp ;											//temp中暂存的结点元素放到合适位置i
	}

template<class Type>
void minHeap<Type>::filterUp(int start){
	//私有函数：从结点start开始到结点0为止,自下向上比较,如果子女的值小
	//于双亲结点的值则相互交换,这样将集合重新调整为最小堆。
	int j = start, i = (j-1)/2;
	Type temp = heap[j];
	while(j>0){												//沿双亲结点路径向上直达根结点
		if (heap[i].key <= temp.key) break;					//双亲结点值小,不调整
		else{	heap[j] = heap[i];
/*				heap[j].key = heap[i].key;
				heap[j].jobID = heap[i].jobID;
				heap[j].jobTime = heap[i].jobTime;*/
				j = i;  i =(i-1)/2;}		//双亲结点值大,调整
    	}
  	heap[j] = temp ;											//回送
	}

template<class Type>int minHeap<Type>::insert (Type &x){
	//if ( currentSize = maxHeapSize) {cerr<<"Heap Full"<<endl; return 0;}//堆满,返回0
  	if ( currentSize == maxHeapSize) {
		maxHeapSize = currentSize+8; 							//堆满,
		heap.reSize(maxHeapSize);}								//加大堆
  	heap[currentSize] = x ;  									//插人
	filterUp (currentSize) ;									//向上调整
  	currentSize++;												//堆计数加1
    return 1;
	}

template<class Type>int minHeap<Type>::removeMin(Type &x){
	if ( ! currentSize) {
		cout<<"Heap empty"<<endl;
		return 0; }  											//空堆,返回0
	x = heap[0];  												//引用参数x带回最小元素
	heap[0] = heap[currentSize-1];							//原来最后元素填补到根结点
    currentSize--;												//堆大小减1
    filterDown (0, currentSize-1 );								//自上向下调整为堆
    return 1;													//成功带回,返回1
    }

enum staff{manager,supervisor,worker};		//职员枚举：0=经理，1=部门主管，2=办事员

//struct jobRequest{
class jobRequest{
	friend ostream& operator<<(ostream& out, jobRequest& jr);
//	friend istream& operator>>(istream& out, jobRequest& jr);
	public:
		jobRequest(){							//无参构造函数
			key = worker;
			jobID = -1;
			jobTime = -1;
			}
		jobRequest(staff k, int i, int t){		//有参构造函数
			key = k;
			jobID = i;
			jobTime = t;
			}
		bDataToFile(ofstream& dist){			//写入二进制数据文件一个作业
			dist.write((char*)&key,sizeof(staff));
			dist.write((char*)&jobID,sizeof(int));
			dist.write((char*)&jobTime,sizeof(int));
			}
//		bDataFromFile(ifstream& sour){			//从二进制数据文件读出一个作业
		int bDataFromFile(ifstream& sour){		//从二进制数据文件读出一个作业
			staff k1 = key;
			int id1 = jobID;
			int ti1 = jobTime;
			sour.read((char*)&key,sizeof(staff));
			sour.read((char*)&jobID,sizeof(int));
			sour.read((char*)&jobTime,sizeof(int));
			if(k1==key && id1==jobID && ti1==jobTime)
				return 0;						//如为末记录自我重复，返回0
			else return 1;
///			sour.read((char*)&key,sizeof(staff));
//			sour.read((char*)&jobID,sizeof(int));
//			sour.read((char*)&jobTime,sizeof(int));
			}
		staff key;								//职员类型staffPerson
//	private:
		int jobID;								//作业号
		int jobTime;							//作业时间
/*	jobRequest& operator=(jobRequest& b){			//无须重载
		key = b.key;
		jobID = b.jobID;
		jobTime = b.jobTime;
	return (*this);
	}*/
	};

ostream& operator<<(ostream& out, jobRequest& jr){
	out<<"staff="<<jr.key<<", jobID="<<jr.jobID<<", jobTime="<<jr.jobTime;
	out<<endl;
	return out;
	}