哈夫曼树

哈夫曼树简介

给定 N 个权值作为 N 个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树( Huffman Tree )。

哈夫曼树涉及的基本概念

路径和路径长度

在一棵树中，从一个结点往下可以达到的孩子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第 L 层结点的路径长度为 L - 1 。

树的带权路径长度

设二叉树具有 n 个带权叶结点，从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和称为 树的带权路径长度（Weighted Path Length of Tree，WPL ）。

设 w 为二叉树第 i 个叶结点的权值，l 为从根结点到第 i 个叶结点的路径长度，则 WPL 计算公式如下：

对于给定一组具有确定权值的叶结点，可以构造出不同的二叉树，其中，WPL 最小的二叉树称为哈夫曼树。
其叶结点权值越小，离根越远，叶结点权值越大，离根越近。

哈夫曼树的构建

哈夫曼树的构建思路

（1）将给定的 n 个节点构建成一个二叉树（初始情况下单个节点看成是一颗二叉树）的集合；
（2）每次在集合中选取最小权值的两个二叉树根节点，并将这两个二叉树将最小的一个作为左子树，次小的一个作为右子树，合并成一个新的二叉树；
（3）将取出的最小的两个二叉树从集合中删除，并将新的二叉树加入到集合中；
（4）重复步骤（2）、（3），最后集合中只剩下一个二叉树时，哈夫曼树构建完成。

构建哈夫曼树图解

（1）

初始化二叉树集合

（2）

最小的 1 和 3 合并为 4

（3）

最小的 4 和 4 合并为 8

（4）

最小的 5 和 6 合并为 11

（5）

最小的 7 和 8 合并为 15

（6）

最小的 9 和 11 合并为 20

（7）

最小的 15 和 20 合并为 35

（8）

计算 WPL

哈夫曼树相关试题

哈夫曼树

Acwing 3531.哈夫曼树

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

int n, ans = 0;
priority_queue<int, vector<int>, greater<int> > heap;  //小根堆

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n;
    while(n--){
        int x; cin>>x;
        heap.push(x);
    }
    
    while(heap.size() > 1){
        int a = heap.top();
        heap.pop();
        int b = heap.top();
        heap.pop();
        
        ans += a + b;
        heap.push(a + b);
    }
    cout<<heap.top()<<endl;
    cout<<ans;
}