minheap.h

本程序中定义了霍夫曼类实现霍夫曼编码和解码

//
// 最小堆定义及实现
//
template<class T>
class MinHeap {
public:
	MinHeap(int MinHeapSize = 10);
	~MinHeap() {delete [] heap;}
	int Size() const {return CurrentSize;}
	T Min() {if (CurrentSize == 0) throw OutOfBounds();
	            return heap[1];}
	MinHeap<T>& Insert(const T& x);
	MinHeap<T>& DeleteMin(T& x);
	void Initialize(T a[], int size, int ArraySize);
	void Deactivate() {heap=0;}
private:
	int CurrentSize, MaxSize;
	T *heap; // 元素数组
};

// 构造函数
template<class T>
MinHeap<T>::MinHeap(int MinHeapSize)
{
	MaxSize = MinHeapSize;
	heap = new T[MaxSize+1];
	CurrentSize = 0;
}

// 最小堆的插入
template<class T>
MinHeap<T>& MinHeap<T>::Insert(const T& x)
{
	if (CurrentSize == MaxSize)
		return *this; //throw NoMem(); // 没有足够空间
    //为x寻找应插入位置
    // i 从新的叶节点开始，并沿着树上升
	int i = ++CurrentSize;
	while (i != 1 && heap[i/2] > x) {
	// 不能够把x放入heap[i]
		heap[i] = heap[i/2]; // 将元素下移
		i /= 2; // 移向父节点
	}
	heap[i] = x;
	return *this;
}

// 最小堆的删除
template<class T>
MinHeap<T>& MinHeap<T>::DeleteMin(T& x)
{// 将最小元素放入x ，并从堆中删除最小元素
// 检查堆是否为空
	if (CurrentSize == 0)
		return *this; //throw OutOfBounds(); // 队列空
	x = heap[1]; // 最小元素
	// 重构堆
	T y = heap[CurrentSize--]; // 最后一个元素
	// 从根开始，为y 寻找合适的位置
	int i = 1, // 堆的当前节点
		ci = 2; // i的孩子
	while (ci <= CurrentSize) {
		// heap[ci] 应是i的较小的孩子
		if (ci < CurrentSize &&
			heap[ci] > heap[ci+1]) ci++;
		// 能把y 放入heap[i]吗?
		if (y <= heap[ci]) break; // 能
		// 不能
		heap[i] = heap[ci]; // 将孩子上移
		i = ci; //下移一层
		ci *= 2;
	}
	heap[i] = y;

	return *this;
}

// 最小堆的初始化
template<class T>
void MinHeap<T>::Initialize(T a[], int size, int ArraySize)
{// 把最小堆初始化为数组a
	delete [] heap;
	heap = a;
	CurrentSize = size;
	MaxSize = ArraySize;
	// 产生一个最小堆
	for (int i = CurrentSize/2; i >= 1; i--) {
		T y = heap[i]; // 子树的根
		// 寻找放置y的位置
		int c = 2*i; // c的父节点是y的目标位置
		while (c <= CurrentSize) {
			// heap[c] 应是较小的同胞节点
			if (c < CurrentSize && heap[c] > heap[c+1]) c++;
			// 能把y放入heap[c/2]吗?
			if (y <= heap[c]) break; // 能
			// 不能
			heap[c/2] = heap[c]; // 将孩子上移
			c *= 2; // 下移一层
		}
		heap[c/2] = y;
	}
}