贪心算法 --- 例题2.哈夫曼编码问题

一.问题描述

Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。
树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作：WPL = Σwi*li (i=1~n)
哈夫曼树，Huffman树定义：在权为w1,w2,…,wn的n个叶子结点的所有二叉树中，带权路径长度WPL最小的二叉树称为赫夫曼树或最优二叉树。
本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。

二.解题思路

哈夫曼树的构造(哈夫曼算法)

• 1.根据给定的n个权值{w1,w2,…,wn}构成二叉树集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树为空.
• 2.在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左右子树根结点的权值之和.
• 3.在F中删除这两棵树,同时将新的二叉树加入F中.
• 4.重复2、3,直到F只含有一棵树为止.(得到哈夫曼树)

代码如下:

// 哈夫曼编码贪心算法实现
// 输入格式
// 输入的第一行包含一个正整数n（n<=100）。
// 接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。
// 输出格式
// 输出用这些数构造Huffman树的总费用。
#include
using namespace std;
int Huffman(int *a, int n)
{
    int ans = 0;
    int pos = 0;
    int temp_n = n;
    while(n>1)
    {
        // sort(a+pos, a+temp_n);
        sort(a, a+temp_n);   
        ans = ans + (a[pos] + a[pos+1]);
        a[pos+1] = a[pos] + a[pos+1];
        pos++;
        n--;
    }
    return ans;
}
int Huffman2(int a[], int n)
{
    int ans = 0;
    sort(a, a+n);
    for(int i=0; i>t;
    while (t--)
    {
        cout<<"输入数组大小:";
        cin>>n; 
        int a[n];
        cout<<"输入数组元素:";
        for(int i=0; i>a[i];
        cout<<"最小哈夫曼构造代价:"<