堆：
堆是STL中priority_queue的最高效的实现方式（关于priority_queue的用法：http://www.cnblogs.com/flyoung2008/articles/2136485.html）。
主要分为大根堆和小根堆。
是一棵完全二叉树。
堆的一次插入删除调整的时间复杂度都是logn。
Huffman树：
又称最优二叉树（带权路径中），带权路径长度最小的二叉树应是权值大的外节点离根结点最近的扩充二叉树（权值都在叶节点的二叉树）就是Huffman树。
算法：
将权值对应的节点全部放入一个小根堆中。
每次取出堆顶的两个节点，构造成一个新的节点，循环n-1次（n为节点数量）。
代码如下：
1 #include<iostream> 2 using namespace std; 3 template<class T> 4 struct TreeNode{ 5 T data;//节点值 6 TreeNode<T> *left,*right,*parent;//左右孩子 7 TreeNode(){ 8 left=NULL; 9 right=NULL; 10 parent=NULL; 11 } 12 TreeNode(T x,TreeNode<T> *l=NULL,TreeNode<T> *r=NULL,TreeNode<T> *p=NULL){ 13 data=x; 14 left=l; 15 right=r; 16 parent=p; 17 } 18 bool operator <=(TreeNode<T> &r){ 19 return data<=r.data; 20 } 21 bool operator <(TreeNode<T> &r){ 22 return data<r.data; 23 } 24 bool operator >=(TreeNode<T> &r){ 25 return data>=r.data; 26 } 27 bool operator >(TreeNode<T> &r){ 28 return data>r.data; 29 } 30 }; 31 32 template<class T> 33 class MinHeap{//最小堆 34 private: 35 T *heap;//堆数组 36 int maxSize;//堆最大容量 37 int currentSize;//当前容量 38 public: 39 MinHeap(int sz=20){ 40 maxSize=sz; 41 heap=new T[maxSize]; 42 currentSize=0; 43 } 44 ~MinHeap(){ 45 delete []heap; 46 } 47 T* getHeap(){ 48 return heap; 49 } 50 void siftDown(int start,int m){//向下调整堆数组 51 int i=start; 52 int j=2*i+1; 53 T temp=heap[i]; 54 while(j<=m){ 55 if(j<m&&*heap[j]>*heap[j+1]) j++; 56 if(*temp<=*heap[j]) break; 57 heap[i]=heap[j]; 58 i=j; 59 j=2*j+1; 60 } 61 heap[i]=temp; 62 } 63 void siftUp(int start){//向上调整堆数组 64 int i=start; 65 int j=(i-1)/2; 66 T temp=heap[i]; 67 while(i>0){ 68 if(*temp>=*heap[j]) break; 69 heap[i]=heap[j]; 70 i=j; 71 j=(i-1)/2; 72 } 73 heap[i]=temp; 74 } 75 bool insert(const T& x){//插入元素 76 if(currentSize==maxSize) return false; 77 heap[currentSize]=x; 78 siftUp(currentSize); 79 currentSize++; 80 return true; 81 } 82 bool remove(T& x){//删除元素 83 if(!currentSize) return false; 84 x=heap[0]; 85 heap[0]=heap[currentSize-1]; 86 currentSize--; 87 siftDown(0,currentSize-1); 88 return true; 89 } 90 }; 91 92 template<class T> 93 class HuffmanTree{ 94 public: 95 HuffmanTree(T w[],int n){//构造Huffman树 96 TreeNode<T> *temp,*first,*second,*parent; 97 MinHeap <TreeNode<T>* >hp; 98 for(int i=0;i<n;i++){ 99 temp=new TreeNode<T>(w[i]); 100 hp.insert(temp); 101 } 102 for(int i=0;i<n-1;i++){ 103 first=new TreeNode<T>; 104 second=new TreeNode<T>; 105 hp.remove(first); 106 hp.remove(second); 107 parent=new TreeNode<T>; 108 merge(first,second,parent); 109 hp.insert(parent); 110 } 111 root=parent; 112 } 113 void merge(TreeNode<T> *first,TreeNode<T> *second,TreeNode<T>* parent){//选取两个最小带权节点合并 114 parent->left=first; 115 parent->right=second; 116 parent->data=first->data+second->data; 117 first->parent=parent; 118 second->parent=parent; 119 } 120 ~HuffmanTree(){ 121 destroy(root); 122 } 123 void destroy(TreeNode<T> *subTree){//递归删除以subTree为根的所有结点 124 if(subTree!=NULL){ 125 destroy(subTree->left); 126 destroy(subTree->right); 127 delete subTree; 128 } 129 } 130 void preOrder(TreeNode<T> *subTree){//前序遍历 131 if(subTree!=NULL){ 132 cout<<subTree->data<<" "; 133 preOrder(subTree->left); 134 preOrder(subTree->right); 135 } 136 } 137 TreeNode<T> *getRoot(){ 138 return root; 139 } 140 private: 141 TreeNode<T> *root; 142 }; 143 144 int main(){ 145 int N,*w; 146 cout<<"输入元素总数："<<endl; 147 cin>>N; 148 w=new int[N]; 149 cout<<"输入这组整数："<<endl; 150 for(int i=0;i<N;i++){ 151 cin>>w[i]; 152 } 153 HuffmanTree<int> *ht=new HuffmanTree<int>(w,N); 154 TreeNode<int> *root=ht->getRoot(); 155 cout<<"Huffman树前序遍历结果:"<<endl; 156 ht->preOrder(root); 157 delete ht,w; 158 return 0; 159 }