贪心 - Huffman 树

定义

对于有 $n$ 个叶子节点的二叉树，定义 $w_i\ge 0$ 为它们的权值，$l_i$ 为从根节点到第 $i$ 个叶子的路径长度，那么带权路径长度 $W$ 定义为：

$$W=\sum_{i=1}^n w_il_i$$

给定一组权值，它们构成的所有树中， $W$ 最小的树就是哈夫曼树。

构造

由给定的 $n$ 个权值创建 $n$ 个只有一个根的二叉树，得到一个二叉树集合 $F$。

当 $|F|\ge2$ 时，取出根节点权值最小的两个树，用一个新的根节点连接他们，这个根的权值是取出的两个树根权值之和。

重复构造至 $|F|=1$ 时得到的树就是 Huffman 树。

为什么？首先，对 $n=1,2$ 时，显然得到的是最优的树。

在 Huffman 树中，将最小的两个 $w_i,w_j$ 调整到相邻的深度最大的地方，答案不会更差。

对 $n$ 个节点的 Huffman 树，假设 $w_1,w_2$ 是最小的两个 $w$，那么一定可以通过调整使得 $w_1,w_2$ 是相邻的深度最大的节点，即：

$$\begin{aligned} W&=\min_{(w_1,\dots,w_n)}\left\{\sum_{i=1}^n w_il_i\right\}\\ &=w_vl_v+\min_{(w_3,\dots,w_n)}\left\{\sum_{i=3}^n w_il_i\right\} \end{aligned}$$

我们每次将 $w_1,w_2$ 合并为 $w_v$ 再放入 $F$ 的过程，就会使得 $l_v$ 最大。

假设 $(i,j)$ 是 $w_i+w_j>w_1+w_2$ 的一对节点。

按照我们的构造，$(1,2)$ 一定会优先于 $(i,j)$ 与某个非严格更小的 $w_k$ 合并，按照类似的思路，$(1,2)$ 的深度一定会 $\ge$ $(i,j)$ 的深度。

如果 $i$ 是叶子节点，它的兄弟不是叶子，那么它的深度会比某个叶子小，所以他的深度比 $(1,2)$ 的深度小。

同样地证明方法可以推广到 $k$ 叉树，只需要一点需要注意：因为每次操作都会减少 $k-1$ 个数，最终剩 $1$ 个，所以需要满足 $(k-1)\mid (n-1)$。

如果不是这样，我们可以增加若干个 $w=0$ 的点，这显然不会影响答案。

Luogu P6033

这就是二叉哈夫曼树最直白的应用。但是，本题并不能用优先队列，会 TLE。

注意到，我们每次都是取出两个最小的数字 $w_1,w_2$ 并把它们插入序列中。

所以我们插入的数字一定是非严格递增的。所以可以维护两个 queue。

Luogu P2168

这是 $k$ 叉哈夫曼树，并且选出 $k$ 个最小的元素，在有相等的情况下尽量让深度小，所以我们以 $w$ 为第一关键字，深度为第二关键字维护即可。