#include <iostream>
#include <queue>
#include <vector>
using namespace std;
//樹結點
struct TreeNode {
	//結點權值
	float weight;
	//左結點
	TreeNode *lelfChild;
	//右結點
	TreeNode *rightChild;
    //初始化
	TreeNode(float w) {
		weight=w;
		lelfChild=NULL;
		rightChild=NULL;
    }
};
//為優(yōu)先隊列提供比較函數(shù)
struct comp {
	bool operator() (TreeNode * a, TreeNode * b) {
        //由大到小排列
		return a->weight > b->weight; 
	}
};

//哈夫曼樹類
class HfmTree {
	private:
         //優(yōu)先隊列容器
		priority_queue<TreeNode *,vector<TreeNode *>,comp> hfmQueue;
	public:
		//構造函數(shù)，構建單根結點樹
		HfmTree(int weights[8]) {
			for(int i=0; i<8; i++) {
				//創(chuàng)建不同權值的單根樹
				TreeNode *tn=new TreeNode(weights[i]);
				hfmQueue.push(tn);
			}
		}
		//顯示隊列中的最一個結點
		TreeNode* showHfmRoot() {
			TreeNode *tn;
			while(!hfmQueue.empty()) {
				tn= hfmQueue.top();
				hfmQueue.pop();
			}
			return tn;
		}
		//構建哈夫曼樹
		void create() {
             //重復直到隊列中只有一個結點
			while(hfmQueue.size()!=1) {
				//從優(yōu)先隊列中找到權值最小的 2 個單根樹
				TreeNode *minFirst=hfmQueue.top();
				hfmQueue.pop();
				TreeNode *minSecond=hfmQueue.top();
				hfmQueue.pop();
				//創(chuàng)建新的二叉樹
				TreeNode *newRoot=new TreeNode(minFirst->weight+minSecond->weight);
				newRoot->lelfChild=minFirst;
				newRoot->rightChild=minSecond;
				//新二叉樹放入隊列中
				hfmQueue.push(newRoot);
			}
		}
		//按前序遍歷哈夫曼樹的所有結點
		void showHfmTree(TreeNode *root) {
			if(root!=NULL) {
				cout<<root->weight<<endl;
				showHfmTree(root->lelfChild);
				showHfmTree(root->rightChild);
			}
		}
		//析構函數(shù)
		~HfmTree() {
            //省略
		}
};

//測試
int main(int argc, char** argv) {
	//不同權值的結點
	int weights[8]= {3,6,12,9,4,8,21,22};
    //調用構造函數(shù)
	HfmTree hfmTree(weights);
    //創(chuàng)建哈夫曼樹
	hfmTree.create();
    //前序方式顯示哈夫曼樹
	TreeNode *root= hfmTree.showHfmRoot();
	hfmTree.showHfmTree(root);
	return 0;
}

#include <iostream>
using namespace std;
//葉結點數(shù)量
const unsigned int n=8;
//一維數(shù)組長度
const unsigned int m= 2*n -1;
//樹結點
struct TreeNode {
	//權值
	float weight;
	//父結點
	int parent;
	//左結點
	int leftChild;
	//右結點
	int rightChild;
};
class HuffmanTree {
	public:
		//創(chuàng)建一維數(shù)組
		TreeNode hfmNodes[m+1];
	public:
		//構造函數(shù)
		HuffmanTree(int weights[8]);
		~HuffmanTree( ) {

		}
		void findMinNode(int k, int &s1, int &s2);
		void showInfo() {
			for(int i=0; i<m; i++) {
				cout<<hfmNodes[i].weight<<endl;
			}
		}
};
HuffmanTree::HuffmanTree(int weights[8]) {
	//前2 個權值最小的結點
	int firstMin;
	int  secondMin;
	//初始化數(shù)組中的結點
	for(int i = 1; i <= m; i++) {
		hfmNodes[i].weight = 0;
		hfmNodes[i].parent = -1;
		hfmNodes[i].leftChild = -1;
		hfmNodes[i].rightChild = -1;
	}
	//前 n 個是葉結點
	for(int i = 1; i <= n; i++)
		hfmNodes[i].weight=weights[i-1];

	for(int i = n + 1; i <=m; i++) {
		this->findMinNode(i-1, firstMin, secondMin);
		hfmNodes[firstMin].parent = i;
		hfmNodes[secondMin].parent = i;
		hfmNodes[i].leftChild = firstMin;
		hfmNodes[i].rightChild = secondMin;
		hfmNodes[i].weight = hfmNodes[firstMin].weight + hfmNodes[secondMin].weight;
	}
}
void HuffmanTree::findMinNode(int k, int & firstMin, int & secondMin) {
	hfmNodes[0].weight = 32767;
	firstMin=secondMin=0;
	for(int i=1; i<=k; i++) {
		if(hfmNodes[i].weight!=0 && hfmNodes[i].parent==-1) {
			if(hfmNodes[i].weight < hfmNodes[firstMin].weight) { 
                  //如果有比第一小還要小的，則原來的第一小變成第二小
				secondMin = firstMin;
                  //新的第一小
				firstMin = i;
			} else if(hfmNodes[i].weight < hfmNodes[secondMin].weight)
			    //如果僅比第二小的小	
                 secondMin = i;
		}
	}
}

int main() {
	int weights[8]= {3,6,12,9,4,8,21,22};
	HuffmanTree huffmanTree(weights);
	huffmanTree.showInfo();
	return 1;
}