[Jobdu] Huffman Tree

Huffman Tree Defination

给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈(霍)夫曼树(Huffman Tree)
Huffman Tree是带权路径长度最短的树,权值较大的结点离根较近

这样描述比较空洞,我们来举个栗子,把下面的数组转为哈夫曼树

[1, 1, 2, 5, 9]

我们把题目都看做树,每个树只有一个root节点,weight为数组中的值

Step 1

选取两个最小权值的树,选取weight最小的两棵树,11,两个子树根节点和为2
将和作为新树root节点的值,两个子树分别成为左右子树,构造成新树

   2  , 2, 5, 9
  / \
 1   1

Setp 2

选取最小两个根节点是22,继续构造

      4   , 5, 9
     / \
    2   2
   / \
  1   1

Step 3

继续…

      9,  9
     / \
    4  5
   / \
  2   2
 / \
1   1

Step 4

完成

        18
       / \
      9   9
     / \
    4   5
   / \
  2   2
 / \
1   1

看明白了吗?没看明白请再看一遍:)

我们来看一个题目吧

题目描述

哈夫曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的层级数与权值的乘积之和。

输入

输入有多组数据。
每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不超过100,2<=n<=1000)。

输出

输出权值。

样例输入

5  
1 2 2 5 9

样例输出

33

思路

上面的栗子和这个样例输入是一样的,我们会发现层级数 * 权值,其实就是所有生成顶点的和

33 = 18 + 9 + 4 + 2

AC代码

int main() { _
    int n;
    int tree[1007];
    while (cin >> n) {
        for (int i = 0; i < n; i++)
            cin >> tree[i];
        int sum = 0;
        for (int i = 1; i < n; i++) {
            sort(tree + i - 1, tree + n);
            sum += (tree[i - 1] + tree[i]);
            tree[i] += tree[i - 1];
        }
        cout << sum << endl;
    }
    return 0;
}