#include "iostream.h"
#include <stdlib.h>
// ----------------------------------------------------------------------------------------------- MinHeap
template <class T>
class MinHeap
{
private:
T *heapArray;
int CurrentSize;
int MaxSize;
void swap(int pos_x, int pos_y);
void BuildHeap();
public:
MinHeap(const int n);
virtual ~MinHeap() {delete [] heapArray;};
bool isLeaf(int pos) const {return (pos >= CurrentSize/2) && (pos < CurrentSize);};
int leftchild(int pos) const {return pos*2 + 1;};
int rightchild(int pos) const {return pos*2 + 2;};
int parent(int pos) const {return (pos - 1) / 2;};
bool Remove(int pos, T&node);
bool Insert(const T&newNode);
T &RemoveMin();
void SiftUp(int position);
void SiftDown(int left);
void DisplayHeap();
};
template <class T>
MinHeap<T>::MinHeap(const int n)
{
if (n <= 0)
return;
CurrentSize = 0;
MaxSize = n;
heapArray = new T[MaxSize];
BuildHeap();
}
template <class T>
void MinHeap<T>::BuildHeap()
{
for (int i = CurrentSize/2 -1; i >= 0; i --)
SiftDown(i);
}
template <class T>
bool MinHeap<T>::Insert(const T &newNode)
{
if (CurrentSize == MaxSize)
return false;
heapArray[CurrentSize] = newNode; // 插再在表尾
SiftUp(CurrentSize);
CurrentSize ++;
return true;
}
template <class T>
void MinHeap<T>::SiftUp(int position)
{
int temppos = position;
T temp = heapArray[temppos];
while ((temppos > 0) && (heapArray[parent(temppos)] > temp))
{
heapArray[temppos] = heapArray[parent(temppos)];
temppos = parent(temppos);
}
heapArray[temppos] = temp;
}
template <class T>
void MinHeap<T>::SiftDown(int left)
{
int i = left;
int j = leftchild(i);
T temp = heapArray[i];
while (j < CurrentSize)
{
if ((j < CurrentSize - 1) && (heapArray[j] > heapArray[j + 1]))
j ++;
if (temp > heapArray[j])
{
heapArray[i] = heapArray[j];
i = j;
j = leftchild(j);
}
else
break;
}
heapArray[i] = temp;
}
template <class T>
void MinHeap<T>::swap(int pos_x, int pos_y)
{
T temp = heapArray[pos_x];
heapArray[pos_x] = heapArray[pos_y];
heapArray[pos_y] = temp;
}
template <class T>
T &MinHeap<T>::RemoveMin()
{
if (CurrentSize == 0)
{
cout << "Can't delete.\n";
exit(1);
}
else
{
swap(0, --CurrentSize);
if (CurrentSize > 1)
SiftDown(0);
return heapArray[CurrentSize];
}
}
template <class T>
bool MinHeap<T>::Remove(int pos, T&node)
{
if (pos < 0 || pos >= CurrentSize)
return false;
T temp = heapArray[pos];
heapArray[pos] = heapArray[--CurrentSize];
SiftUp(pos);
SiftDown(pos);
node = temp;
return true;
}
template <class T>
void MinHeap<T>::DisplayHeap()
{
T temp;
int j = CurrentSize;
for (int i = 0; i < j; i ++)
{
temp = RemoveMin();
cout << temp << " ";
}
cout << "\n\n";
}
// ----------------------------------------------------------------------------------------------- MinHeap
// ----------------------------------------------------------------------------------------------- Huffman
template <class T> class HuffmanTree;
template <class T>
class HuffmanTreeNode
{
friend class HuffmanTree<T>;
private:
T element;
HuffmanTreeNode<T> *parent;
HuffmanTreeNode<T> *left;
HuffmanTreeNode<T> *right;
public:
HuffmanTreeNode() {};
HuffmanTreeNode<T> *leftchild() {return left};
HuffmanTreeNode<T> *rightchild() {return right;};
bool operator > (HuffmanTreeNode<T> &HN) {return element > HN.element;}; // 注意要重载运算
bool operator < (HuffmanTreeNode<T> &HN) {return element < HN.element;};
bool operator == (HuffmanTreeNode<T> &HN) {return element == HN.element;};
};
template <class T>
class HuffmanTree
{
private:
HuffmanTreeNode<T> *root;
public:
HuffmanTree(T weight[], int n);
virtual ~HuffmanTree() {DeleteTree(root);};
void MergeTree(HuffmanTreeNode<T> &ht1, HuffmanTreeNode<T> &ht2, HuffmanTreeNode<T> *parent);
void DeleteTree(HuffmanTreeNode<T> *root);
void InOrder(HuffmanTreeNode<T> *root);
HuffmanTreeNode<T> *GetRoot() {return root;};
};
template <class T>
void HuffmanTree<T>::DeleteTree(HuffmanTreeNode<T> *root)
{
if (root)
{
DeleteTree(root->left);
DeleteTree(root->right);
delete root;
}
}
template <class T>
void HuffmanTree<T>::InOrder(HuffmanTreeNode<T> *root)
{
if (root)
{
InOrder(root->left);
cout << root->element << " ";
InOrder(root->right);
}
}
template <class T>
void HuffmanTree<T>::MergeTree(HuffmanTreeNode<T> &ht1, HuffmanTreeNode<T> &ht2, HuffmanTreeNode<T> *parent)
{
HuffmanTreeNode<T> *l = new HuffmanTreeNode<T>();
HuffmanTreeNode<T> *r = new HuffmanTreeNode<T>();
*l = ht1; // 不能写为l = &ht1，注意地址引用，开辟的是新空间，或者应用拷贝构造函数，只是有写麻烦
*r = ht2;
parent->parent = NULL;
parent->left = l;
parent->right = r;
parent->element = ht1.element + ht2.element;
ht1.parent = ht2.parent = parent; // 指向父节点
}
template <class T>
HuffmanTree<T>::HuffmanTree(T weight[], int n)
{
MinHeap<HuffmanTreeNode<T> > heap(n); // 注意..>>之间隔开
HuffmanTreeNode<T> *parent, firstchild, secodechild, firstchild1, secodechild1;
HuffmanTreeNode<T> *NodeList = new HuffmanTreeNode<T>[n];
for (int i = 0; i < n; i ++)
{
NodeList[i].element = weight[i];
NodeList[i].parent = NodeList[i].left = NodeList[i].right = NULL;
heap.Insert(NodeList[i]);
}
for (i = 0; i < n-1; i ++)
{
parent = new HuffmanTreeNode<T>();
firstchild = heap.RemoveMin();
secodechild = heap.RemoveMin();
MergeTree(firstchild, secodechild, parent); // 合并树
heap.Insert(*parent);
root = parent;
}
delete []NodeList;
}
void main()
{
int weight[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41};
int n = sizeof(weight)/sizeof(int);
HuffmanTree<int> aHT(weight, n);
aHT.InOrder(aHT.GetRoot());
}
