8. 哈夫曼树的应用

题目来源和说明

2010年北京邮电大学计算机研究生机试真题，我们以这个题为例梳理和总结哈夫曼树的应用。

题目链接：https://www.nowcoder.com/practice/162753046d5f47c7aac01a5b2fcda155?tpId=67&tqId=29635&tPage=1&ru=/kaoyan/retest/1005&qru=/ta/bupt-kaoyan/question-ranking

题目描述

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

样例

输入：
5  
1 2 2 5 9
复制
输出：
37

简要分析

我们每次都从集合K总选出两个权值最小的节点，这不妨让我们想到了最小堆的性质。于是我们可以直接使用stl的最小堆实现的优先级队列，每次pop出两个最小的，然后加起来形成的新节点再push进去就行，这样时间复杂度也变小O（logn）

注意

priority_queue<int> Q;//这样建立的堆默认为最大堆，因此不适合哈夫曼树
priority_queue<int,vector<int>,greater<int>> Q;这样定义的是一个最小堆

C++ 代码

#include<iostream>
#include<queue>
using namespace std;

priority_queue<int,vector<int>,greater<int>> Q; //建立一个小顶堆

int main() {
    int n;
    while(scanf("%d",&n)!=EOF) {
        while(Q.empty()==false) Q.pop(); //清空
        for(int i=1;i<=n;i++) {
            int x;
            scanf("%d",&x);
            Q.push(x); //吧权值放入堆中，会自动维护小顶堆的性质
        }
        int ans=0;
        while(Q.size()>1) {
            int a=Q.top();//取堆顶，即最小的
            Q.pop(); //探出
            int b=Q.top();//取堆顶，即最小的
            Q.pop();
            ans+=a+b; 
            Q.push(a+b);
        }
        printf("%d\n",ans);
    }
    return 0;
}

同类题目

1. 搬水果

https://www.nowcoder.com/questionTerminal/e4c775b0f3ee42a4bb72c26d2e1eef8a

简要分析

拿到这道题目，首先想到的是贪心的思想，我总是选择两堆重量最小的，这样是局部最优解。那这就回到了我们的例题。从一个集合K总选择两个最小的，并将其和返回集合K总，这就是哈夫曼树的概念。具体的代码如下：

C++代码

#include<iostream>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int>> Q;
int main() {
    int n;
    while(scanf("%d",&n)!=EOF&&n!=0) {
        while(!Q.empty()) Q.pop(); //清空
        for(int i=0;i<n;i++) {
            int x;scanf("%d",&x);
            Q.push(x);
        }
        int ans=0;
        while(Q.size()>1) {
            int a=Q.top();Q.pop();
            int b=Q.top();Q.pop();
            ans+=a+b;
            Q.push(a+b);
        }
        printf("%d\n",ans);
    }
    return 0;
}