哈夫曼树以及哈夫曼编码

本文主要是介绍哈夫曼树以及哈夫曼编码，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、问题描述

构造一颗包含\(n\)个叶子节点的\(k\)叉树，其中第\(i\)个叶子节点带有权值\(w_i\)，要求最小化\(\sum w_i*l_i\)，其中\(l_i\)表示第\(i\)个叶子节点到根节点的距离。

二、算法描述

运用贪心的思想，权值大的叶子结点的深度一定要小。
先考虑\(k=2\)的情况，我们不难想出一种贪心算法：
1.建立一个小根堆，插入这\(n\)个叶子节点的权值。
2.从堆中取出最小的两个权值\(w_1\)和\(w_2\)，令\(ans+=w_1+w_2\)。
3.建立一个新的节点\(p\)，权值为\(w_1+w_2\)，令\(p\)成为取出的两个节点的父亲。
4.在堆中插入权值\(w_1+w_2\)。
5.重复第\(2~4\)步，直到堆得大小为\(1\)。
Luogu P1090

接着再扩展到\(k>2\)的情况：

这篇关于哈夫曼树以及哈夫曼编码的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！