贪心算法 — 例题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<bits/stdc++.h>
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<n-1; i++)
    {
        ans += (a[i]+a[i+1]);
        a[i+1] += a[i];
        sort(a, a+n);
    }
    return ans;
}
int main()
{
    int t, n;
    cin>>t;
    while (t--)
    {
        cin>>n; 
        int a[n];
        for(int i=0; i<n; i++) cin>>a[i];
        cout<<Huffman2(a, n)<<endl;
    }
    system("pause");
    return 0;    
}

参考毕方明老师《算法设计与分析》课件.

欢迎大家访问个人博客网站—乔治的编程小屋,和我一起为大厂offer努力!