heap.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

//最小堆类
#ifndef HItemAP_H
#define HItemAP_H
#include<iostream>
//using namespace std;
const int DefaultSize=10;
template <class T, class Item>
class MinHeap
{
public:
	MinHeap(int sz = DefaultSize);			//构造函数：建立空堆
	MinHeap(Item arr[], int n);				//构造函数：通过一个数组建堆
	~MinHeap() {delete []heap;}			//析构函数
	bool Insert(const Item& x);				//将x插入到最小堆中
	bool RemoveMin(Item& x);					//删除堆顶上的最小元素
	bool IsEmpty()const						//判堆空否? 空返回1,否则0
	{return (currentSize == 0) ? true : false;}
	bool IsFull()const						//判堆满否? 满则返回1, 否则0
	{return (currentSize == maxHeapSize) ? true : false;}	
	void MakeEmpty() {currentSize = 0;}	//置空堆
	void show()//输出最小堆元素
	{
		for(int i = 0; i<currentSize; i++)
			cout<<heap[i]<<" ";
		cout<<endl;
	}
private: 
	Item *heap;								//存放最小堆中元素的数组
	int currentSize;						//最小堆中当前元素个数
	int maxHeapSize;						//最小堆最多允许元素个数
	void siftDown(int start, int m);		//从start到m下滑调整成为最小堆
	void siftUp(int start);					//从start到0上滑调整成为最小堆
};

template <class T, class Item>
MinHeap<T,Item>::MinHeap(int sz) {
	maxHeapSize = (DefaultSize < sz) ? sz : DefaultSize;
	heap = new Item[maxHeapSize];				//创建堆存储空间
	if (heap == NULL) {cerr << "堆存储分配失败!"<< endl;  exit(1);}
	currentSize = 0;						//建立当前大小
};

template <class T, class Item>
MinHeap<T,Item>::MinHeap(Item arr[], int n) {
	maxHeapSize = (DefaultSize < n) ? n : DefaultSize;	
	heap = new Item[maxHeapSize]; 
	if (heap == NULL) {cerr << "堆存储分配失败！"<< endl;  exit(1);}
	for (int i = 0; i < n; i++ ) heap[i] = arr[i];
	currentSize = n;							//复制堆数组, 建立当前大小
	int currentPos = (currentSize-2)/2;		//找最初调整位置:最后分支结点
	while (currentPos >= 0) {					//自底向上逐步扩大形成堆
		siftDown(currentPos, currentSize -1);	//局部自上向下下滑调整
		currentPos--;							//再向前换一个分支结点
	}
};

template <class T, class Item>
void MinHeap<T,Item>::siftDown(int start, int m) {
	//私有函数: 从结点start开始到m为止, 自上向下比较, 如果子女的值小于父结点的值,
	//则关键码小的上浮, 继续向下层比较, 这样将一个集合局部调整为最小堆。
	int i = start,   j = 2*i+1;  				//j是i的左子女位置
	Item temp = heap[i]; 			
	while (j <= m) {							//检查是否到最后位置
		if (j < m && heap[j] > heap[j+1]) j++;	//让j指向两子女中的小者
		if (temp <= heap[j]) break;				//小则不做调整
		else {heap[i] = heap[j];  i = j; j = 2*j+1; }
		//否则小者上移, i,j下降
	}
	heap[i] = temp;								//回放temp中暂存的元素
};

template <class T, class Item>
void MinHeap<T,Item>::siftUp(int start) {
	//私有函数: 从结点start开始到结点0为止, 自下向上比较, 如果子女的值小于父结点的值
	//则相互交换, 这样将集合重新调整为最小堆。关键码比较符“<=”在Item中定义。
	int j = start,  i = (j-1)/2;   Item temp = heap[j];
	while (j > 0) {								//沿父结点路径向上直达根
		if (heap[i] <= temp) break;				//父结点值小, 不调整
		else {heap[j] = heap[i];  j = i;  i = (i-1)/2; }
		//父结点结点值大, 调整
	}
	heap[j] = temp;								//回送
};

template <class T, class Item>
bool MinHeap<T,Item>::Insert(const Item& x) {
	//公共函数: 将x插入到最小堆中
	if (currentSize == maxHeapSize)
	{cerr << "Heap Full" << endl;  return false;}	//堆满
	heap[currentSize] = x;  					//插入
	siftUp(currentSize);						//向上调整
	currentSize++;								//堆计数加1
	return true;
};
template <class T, class Item>
bool MinHeap<T,Item>::RemoveMin(Item& x) {
	if (!currentSize) {cout << "Heap empty" << endl;  return false;}
	//堆空, 返回false
	x = heap[0];  heap[0] = heap[currentSize-1];	//最后元素填补到根结点
	currentSize--;
	siftDown(0, currentSize-1);						//自上向下调整为堆
	return true;									//返回最小元素
};

#endif;