算法学习 - Huffman树

题目：输入N个权值（1-100正整数），建立哈夫曼树

Note:
一次遍历找出序列中最小数和次小数：

1. 如果序列只有一个数，返回这个数
2. 遍历这个序列，对每个数：
3. 如果这个数比最小数小，更新原来的次小数为最小数，更新原来的最小数为这个数；
4. 如果这个数不比最小数小，但比次小数小，更新原来的次小数为这个数。

#include <iostream>

using namespace std;

typedef struct Node{
	int weight = 0;
	int parent = -1;
	int child_l = -1;
	int child_r = -1;
} Node;

#define MAX_INT 100000000

void print(Node* huffmam_tree, int n) {
	// print huffman tree
	printf("节点\t权值\t父节点\t左孩子\t右孩子\n");
	for(int i=0; i<n*2-1; i++) {
		auto node = huffmam_tree[i];
		cout << i << "\t" << node.weight << "\t" << node.parent << "\t" << node.child_l << "\t" << node.child_r << "\n";
	}
}

int main() {
	// int n;
	// cin >> n;
	// int weights[100];
	// for(int i=0;i<n;i++){
	// 	cin >> weights[i];
	// }

	int n = 5;
	int weights[5] = {1,2,3,4,5};

	Node* huffmam_tree = new Node[2*n - 1];
	for(int i=0; i<n; i++) {
		huffmam_tree[i].weight = weights[i];
	}
	
	// build huffman tree
	for(int i=n; i<2*n-1; i++) {
		int min_1=MAX_INT, min_2=MAX_INT, min_1_id=0, min_2_id=0;
		for(int j=0; j<i; j++) {
			if(huffmam_tree[j].parent == -1) { // No parent
				if(huffmam_tree[j].weight < min_1) {
					// 如果当前元素比最小数还小，那么原来的最小数变成次小数，当前元素变成新的最小数。
					// set min_2 as last min_1
					min_2 = min_1;
					min_2_id = min_1_id;
					// set min_1 as newer minimum node
					min_1 = huffmam_tree[i].weight;
					min_1_id = j;
				} else if (huffmam_tree[j].weight < min_2) {
					// 如果当前元素比最小数大但比次小数小，那么当前元素变成新的次小数。
					min_2_id = j;
					min_2 = huffmam_tree[j].weight;
				}
			}
		}
		// set new node
		huffmam_tree[i].weight = huffmam_tree[min_1_id].weight + huffmam_tree[min_2_id].weight;
		huffmam_tree[i].child_l = min_1_id;
		huffmam_tree[i].child_r = min_2_id;
		// set parent for min_1 and min_2
		huffmam_tree[min_1_id].parent = i;
		huffmam_tree[min_2_id].parent = i;
	}

	print(huffmam_tree, n);
	
	
	return 0;
}