基本数据结构 | 二叉堆

参考《算法竞赛进阶指南》、AcWing题库

二叉堆

二叉堆是一种支持插入、删除、查询最值的数据结构。它其实是一棵满足“堆性质” 的完全二叉树, 树上的每个节点带有一个权值。

完全二叉树：叶子节点都在最后两层，且在最后一层集中于左侧的二叉树。

若树中的任意一个节点的权值都小于等于其父节点的权值, 则称该二叉树满足 “大根堆性质”。若树中任意一个节点的权值都大于等于其父节点的权值, 则称该二叉树满足 “小根堆性质” 。满足 “大根堆性质” 的完全二叉树就是 “大根堆”, 而满足 “小根堆性质” 的完全二叉树就是 “小根堆” , 二者都是二叉堆的形态之一。

根据完全二叉树的性质, 我们可以采用层次序列存储方式, 直接用一个数组来保存二叉堆。层次序列存储方式, 就是逐层从左到右为树中的节点依次编号, 把此编号作为节点在数组中存储的位置 (下标)。在这种存储方式中, 父节点编号等于子节点编号除以 2 , 左子节点编号等于父节点编号乘 2 , 右子节点编号等于父节点编号乘 2 加 1 , 如下图所示。

我们以大根堆为例探讨堆支持的几种常见操作的实现。

Insert

$Insert (val)$ 操作向二叉堆中插入一个带有权值 $val$ 的新节点。我们把这个新节点直接放在存储二叉堆的数组末尾, 然后通过交换的方式向上调整, 直至满足堆性质。其时间复杂度为堆的深度, 即 $O(\log N)$ 。

int heap[SIZE], idx; // 1 是堆顶

void up(int u) {
	while (u / 2 && heap[u] > heap[u / 2]) {
		swap(heap[u], heap[u / 2]);
		u /= 2;
	}	
}

void insert(int val) {
	heap[++idx] = val;
	up(idx);
}

GetTop

$GetTop$ 操作返回二叉堆的堆顶权值，即最大值 $heap[1]$ ，复杂的为 $O(1)$

int getTop() {
	return heap[1];
}

RemoveTop

$RemoveTop$ 操作把堆顶从二叉堆中移除。我们把堆顶 $heap[1]$ 与存储在数组末尾的节点 $heap[n]$ 交换, 然后移除数组末尾节点 (令 $n$ 减小 1), 最后把堆顶通过交换的方式向下调整, 直至满足堆性质。其时间复杂度为堆的深度, 即 $O(\log N)$ 。

void down(int u) {
	int t = u, ls = u << 1, rs = u << 1 | 1;
	if (ls <= idx && heap[t] < heap[ls]) t = ls;
	if (rs <= idx && heap[t] < heap[rs]) t = rs;
	if (t != u) {
		swap(t, u);
		down(t);
	}
}

void removeTop() {
	heap[1] = head[idx--];
	down(1);
}

Romove

$\operatorname{Remove}(p)$ 操作把存储在数组下标 $p$ 位置的节点从二叉堆中删除。与 RemoveTop 相类似, 我们先把 $heap[p]$ 与 $heap[n]$ 交换, 然后令 $n$ 减小 1 。注意此时 $heap[p]$ 既有可能需要向下调整, 也有可能需要向上调整, 需要分别进行检查和处理。时间复杂度 为 $O(\log N)$ 。

void remove(int k) {
	heap[k] = heap[idx--];
	up(k), down(k);
}

C++ STL中的 priority_queue (优先队列) 为实现了一个大根堆, 支持 $push (Insert)$, $top (GetTop)$ 和 $pop (RemoveTop)$ 操作, 不支持 $Remove$ 操作。

---

例题

145. 超市

超市里有 $N$ 件商品，每件商品都有利润 $p_i$ 和过期时间 $d_i$，每天只能卖一件商品，过期商品不能再卖。

求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。

输入格式

输入包含多组测试用例。

每组测试用例，以输入整数 $N$ 开始，接下来输入 $N$ 对 $p_i$ 和 $d_i$，分别代表第 $i$ 件商品的利润和过期时间。

在输入中，数据之间可以自由穿插任意个空格或空行，输入至文件结尾时终止输入，保证数据正确。

输出格式

对于每组产品，输出一个该组的最大收益值。

每个结果占一行。

数据范围

$0 \le N \le 10000$,
$1 \le p_i,d_i \le 10000$
最多有 $14$ 组测试样例

输入样例：

4  50 2  10 1   20 2   30 1

7  20 1   2 1   10 3  100 2   8 2
   5 20  50 10 

输出样例：

80
185 

算法分析

容易想到一个贪心策略：在最优解中, 对于每个时间 (天数) $t$, 应该在保证不卖出过期商品的前提下, 尽量卖出利润前 $t$ 大的商品。因此, 我们可以依次考虑每个商品, 动态维护一个满足上述性质的方案。

详细地说, 我们把商品按照过期时间排序, 建立一个初始为空的小根堆 (节点权值为商品利润), 然后扫描每个商品:

1. 若当前商品的过期时间 (天数) $t$ 等于当前堆中的商品个数, 则说明在目前方案下, 前 $t$ 天已经安排了 $t$ 个商品卖出。此时, 若当前商品的利润大于堆顶权值 (即已经安排的 $t$ 个商品中的最低利润), 则替换掉堆顶 (用当前商品替换掉原方案中利润最低的商品)。
2. 若当前商品的过期时间 (天数) 大于当前堆中的商品个数, 直接把该商品插入堆。

最终, 堆里的所有商品就是我们需要卖出的商品, 它们的利润之和就是答案。该算法的时间复杂度为 $O(N \log N)$ 。

//Author:XuHt
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10006;
int n;
pair<int, int> a[N];
priority_queue<int> q;

void Supermarket() {
	for (int i = 1; i <= n; i++)
		scanf("%d %d", &a[i].second, &a[i].first);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		if (a[i].first == q.size() && -q.top() < a[i].second) {
			q.pop();
			q.push(-a[i].second);
			continue;
		}
		if (a[i].first > q.size()) q.push(-a[i].second);
	}
	int ans = 0;
	while (q.size()) {
		ans += q.top();
		q.pop();
	}
	cout << -ans << endl;
}

int main() {
	while (cin >> n) Supermarket();
	return 0;
}

Solution

---

146. 序列（Top K，多路归并）

给定 $m$ 个序列，每个包含 $n$ 个非负整数。

现在我们可以从每个序列中选择一个数字以形成具有 $m$ 个整数的序列。

很明显，我们一共可以得到 $n^m$ 个这种序列，然后我们可以计算每个序列中的数字之和，并得到 $n^m$ 个值。

现在请你求出这些序列和之中最小的 $n$ 个值。

输入格式

第一行输入一个整数 $T$，代表输入中包含测试用例的数量。

接下来输入 $T$ 组测试用例。

对于每组测试用例，第一行输入两个整数 $m$ 和 $n$。

接下在 $m$ 行输入 $m$ 个整数序列，数列中的整数均不超过 $10000$。

输出格式

对于每组测试用例，均以递增顺序输出最小的 $n$ 个序列和，数值之间用空格隔开。

每组输出占一行。

数据范围

$0 < m \le 1000$,
$0 < n \le 2000$

输入样例：

1
2 3
1 2 3
2 2 3 

输出样例：

3 3 4 

算法分析

先来考虑当 $M=2$ 时的简化问题, 即从 2 个序列中任取一个数相加构成的 $N^{2}$ 个和中求出前 $N$ 小的和。设这两个序列为 $A$ 和 $B$, 把它们分别排序。

可以发现, 最小和一定是 $A[1]+B[1]$, 次小和是 $\min (A[1]+B[2], A[2]+B[1])$ 。假设次小和是 $A[2]+B[1]$, 那么第 3 小和就是 $A[1]+B[2], A[2]+B[2], A[3]+B[1]$ 三者之一。也就是说, 当确定 $A[i]+B[j]$ 为第 $k$ 小和后, $A[i+1]+B[j]$ 与 $A[i]+B[j+1]$ 就加入了第 $k+1$ 小和的备选答案集合。读者可以类比有两个指针分别指向 $A[i]$ 和 $B[j]$, 把其中一个指针向后移动一位, 就可能产生下一个和。

需要注意的是, $A[1]+B[2]$ 与 $A[2]+B[1]$ 都能产生 $A[2]+B[2]$ 这个备选答案。为了避免重复, 我们可以规定: 如果把 $j$ 加 1 产生新的备选答案, 那么以后只能再增加 $j$, 不能再增加 $i$ 。也就是说, 从 $A[1]+B[1]$ 到任何 $A[i]+B[j]$ 必须先向后移动指向 $A$ 的指针 $i$, 再向后移动指向 $B$ 的指针 $j$, 这样就可以保证备选答案产生路线的唯一性。

我们建立一个小根堆, 堆中每个节点存储一个三元组 $(i, j, l a s t)$, 其中 $last$ 表示上一次移动的指针是不是 $j$, 堆的比较操作以 $A[i]+B[j]$ 作为节点权值。

起初, 堆中只有 $(1,1, false)$ 。

取出堆顶 $(i, j,last)$, 然后把 $(i, j+1,true)$ 插入堆, 如果 $last$ 为 $false$, 再把 $(i+1, j, false)$ 也插入堆。

重复上一步 $N$ 次, 每次取出的堆顶节点的权值 $A[i]+B[j]$ 一起构成前 $N$ 小和。该算法的时间复杂度为 $O(N \log N)$ 。

回到本题, 根据数学归纳法, 我们可以先求出前 2 个序列中任取一个数相加构成的前 $N$ 小和, 把这 $N$ 个和作为一个序列, 再与第 3 个序列求新的前 $N$ 小和, 依此类推, 最终得到 $M$ 个序列任取一个数相加构成的前 $N$ 小和。整个算法的时间复杂度为 $\mathrm{O}(M N \log N)$ 。

//Author:XuHt
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2006;
int m, n, f[N], a[N], b[N];
priority_queue<pair<int, pair<int, int>>> q;

void work() {
	priority_queue<pair<int, pair<int, int>>> w;
	swap(w, q);
	q.push(make_pair(- a[1] - b[1], make_pair(1, 1)));
	for (int i = 1; i <= n; i++) {
		f[i] = -q.top().first;
		int x = q.top().second.first, y = q.top().second.second;
		q.pop();
		if (y == 1) q.push(make_pair(- a[x+1] - b[y], make_pair(x + 1, y)));
		q.push(make_pair(- a[x] - b[y+1], make_pair(x, y + 1)));
	}
}

void Sequence() {
	cin >> m >> n;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	--m;
	while (m--) {
		for (int j = 1; j <= n; j++) scanf("%d", &b[j]);
		sort(b + 1, b + n + 1);
		work();
		memcpy(a, f, sizeof(a));
	}
	for (int i = 1; i <= n; i++) printf("%d ", a[i]);
	cout << endl;
}

int main() {
	int t;
	cin >> t;
	while (t--) Sequence();
	return 0;
}

Solution

---

147. 数据备份

你在一家 IT 公司为大型写字楼或办公楼的计算机数据做备份。

然而数据备份的工作是枯燥乏味的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。

已知办公楼都位于同一条街上，你决定给这些办公楼配对（两个一组）。

每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。

然而，网络电缆的费用很高。

当地电信公司仅能为你提供 $K$ 条网络电缆，这意味着你仅能为 $K$ 对办公楼（总计 $2K$ 个办公楼）安排备份。

任意一个办公楼都属于唯一的配对组（换句话说，这 $2K$ 个办公楼一定是相异的）。

此外，电信公司需按网络电缆的长度（公里数）收费。

因而，你需要选择这 $K$ 对办公楼使得电缆的总长度尽可能短。

换句话说，你需要选择这 $K$ 对办公楼，使得每一对办公楼之间的距离之和（总距离）尽可能小。

下面给出一个示例，假定你有 $5$ 个客户，其办公楼都在一条街上，如下图所示。

这 $5$ 个办公楼分别位于距离大街起点 $1km, 3km, 4km, 6km$ 和 $12km$ 处。

电信公司仅为你提供 $K=2$ 条电缆。

上例中最好的配对方案是将第 $1$ 个和第 $2$ 个办公楼相连，第 $3$ 个和第 $4$ 个办公楼相连。

这样可按要求使用 $K=2$ 条电缆。

第 $1$ 条电缆的长度是 $3km-1km=2km$，第 $2$ 条电缆的长度是 $6km-4km=2km$。

这种配对方案需要总长 $4km$ 的网络电缆，满足距离之和最小的要求。

输入格式

第一行输入整数 $n$ 和 $K$，其中 $n$ 表示办公楼的数目，$K$ 表示可利用的网络电缆的数目。

接下来的 $n$ 行每行仅包含一个整数 $s$，表示每个办公楼到大街起点处的距离。

这些整数将按照从小到大的顺序依次出现。

输出格式

输出应由一个正整数组成，给出将 $2K$ 个相异的办公楼连成 $K$ 对所需的网络电缆的最小总长度。

数据范围

$2 \le n \le 100000$,
$1 \le K \le n/2$,
$0 \le s \le 1000000000$

输入样例：

5 2 
1
3
4
6
12 

输出样例：

4 

算法分析

我们很容易发现, 最优解中每两个配对的办公楼一定是相邻的。我们求出每两个相邻办公楼之间的距离, 记为 $D_{1}, D_{2}, D_{3}, \cdots, D_{N-1}$ 。于是问题可以转化为: 从数列 $D$ 中选出不超过 $K$ 个数 (对应办公楼的 $K$ 个配对), 使它们的和最小, 并且相邻的两个数不能同时被选 (任一办公楼都属于唯一的配对组)。

如果 $K=1$, 答案显然是 $D$ 数列中的最小值。
如果 $K=2$, 答案一定是以下两种情况之一：

1. 选择最小值 $D_{i}$, 以及除了 $D_{i-1}, D_{i}, D_{i+1}$ 之外其他数中的最小值。
2. 选择最小值 $D_{i}$ 左右两侧的两个数, 即 $D_{i-1}$ 和 $D_{i+1}$ 。

这很容易证明: 如果 $D_{i-1}$ 和 $D_{i+1}$ 都没有选, 那么不选最小值 $D_{i}$ 一定不优; 如果 $D_{i-1}$ 和 $D_{i+1}$ 选了一个, 那么把选了的那个换成 $D_{i}$, 答案也会变小, 所以最优解必定是上面两种情况之一。

通过上述证明, 我们也可以得到一个推论: 在最优解中, 最小值左右两侧的数要么同时选, 要么都不选。

因此, 我们可以先选上 $D$ 数列中的最小值, 然后把 $D_{i-1}, D_{i}, D_{i+1}$ 从 $D$ 数列中删除, 把 $D_{i-1}+D_{i+1}-D_{i}$ 插入到 $D$ 数列中刚才执行删除的位置。最后, 求解 “从新的 $D$ 数列中选出不超过 $K-1$ 个数, 使它们的和最小, 并且相邻两个数不能同时被选” 这个子问题。

在这个子问题中, 如果选了 $D_{i-1}+D_{i+1}-D_{i}$ 这个数, 相当于去掉 $D_{i}$, 换上 $D_{i-1}$ 和 $D_{i+1}$; 如果没选, 那么刚才选择最小值 $D_{i}$ 显然是一步最优策略。这恰好涵盖了我们在推论中提到的最优解当中的两种情况。

综上所述, 我们得到了这样一个算法:

建立一个链表 $L$, 连接 $N-1$ 个节点, 节点上分别记录数值 $D_{1}, D_{2}, D_{3}, \cdots, D_{N-1}$, 即每两个相邻办公楼之间的距离。再建立一个小根堆, 与链表构成映射关系 (就是说堆中也有 $N-1$ 个节点, 节点权值分别是 $D_{1}, D_{2}, D_{3}, \cdots, D_{N-1}$, 并且同时记录对应的链表节点的指针）。

取出堆顶, 把权值累加到答案中。设堆顶对应链表节点的指针为 $p$, 数值为 $L(p)$ 。在链表中删除 $p, p\rightarrow prev$ 和 $p\rightarrow next$, 在同样的位置插入一个新节点 $q$, 记录数值 $L(q)=L(p\rightarrow prev )+L(p\rightarrow next )-L(p)$ 。在堆中也同时删除对应 $p\rightarrow prev$ 和 $p\rightarrow next$ 的节点, 插入对应链表节点 $q$, 权值为 $L(q)$ 的新节点。

重复上述操作 $K$ 次, 就得到了最终的答案。

Solution

---

Huffman 树

考虑这样一个问题: 构造一棵包含 $n$ 个叶子节点的 $k$ 叉树, 其中第 $i$ 个叶子节点带有权值 $w_{i}$, 要求最小化 $\sum w_{i} * l_{i}$, 其中 $l_{i}$ 表示第 $i$ 个叶子节点到根节点的距离。该问题的解被称为 $k$ 叉 Huffman 树 (哈夫曼树)。

为了最小化 $\sum w_{i} * l_{i}$, 应该让权值大的叶子节点的深度尽量小。当 $k=2$ 时, 我们很容易想到用下面这个贪心算法来求出二叉 Huffman 树。

1. 建立一个小根堆, 插入这 $n$ 个叶子节点的权值。
2. 从堆中取出最小的两个权值 $w_{1}$ 和 $w_{2}$, 令 $ans \;+=w_{1}+w_{2}$ 。
3. 建立一个权值为 $w_{1}+w_{2}$ 的树节点 $p$, 令 $p$ 成为权值为 $w_{1}$ 和 $w_{2}$ 的树节点的父亲。
4. 在堆中插入权值 $w_{1}+w_{2}$ 。
5. 重复第 $2 \sim 4$ 步, 直至堆的大小为 1 。

最后, 由所有新建的 $p$ 与原来的叶子节点构成的树就是 Huffman 树, 变量 ans 就是 $\sum w_{i} * l_{i}$ 的最小值。

对于 $k(k>2)$ 叉 Huffman 树的求解, 直观的想法是在上述贪心算法的基础上, 改为每次从堆中取出最小的 $k$ 个权值。然而, 仔细思考可以发现, 如果在执行最后一 轮循环时, 堆的大小在 $2 \sim k-1$ 之间 (不足以取出 $k$ 个), 那么整个 Huffman 树的根的子节点个数就小于 $k$ 。这显然不是最优解一一我们任意取 Huffman 树中一个深度最大的节点, 把它改为树根的子节点, 就会使 $\sum w_{i} * l_{i}$ 变小。

因此, 我们应该在执行上述贪心算法之前, 补加一些额外的权值为 0 的叶子节点, 使叶子节点的个数 $n$ 满足 $(n-1) \bmod (k-1)=0$ 。也就是说, 我们让子节点不足 $k$ 个的情况发生在最底层, 而不是根节点处。在 $(n-1) \bmod (k-1)=0$ 时, 执行 “每次从堆中取出最小的 $k$ 个权值” 的贪心算法就是正确的。

148. 合并果子

在一个果园里，达达已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。

达达决定把所有的果子合成一堆。

每一次合并，达达可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。

可以看出，所有的果子经过 $n-1$ 次合并之后，就只剩下一堆了。

达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以达达在合并果子时要尽可能地节省体力。

假定每个果子重量都为 $1$，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使达达耗费的体力最少，并输出这个最小的体力耗费值。

例如有 $3$ 种果子，数目依次为 $1，2，9$。

可以先将 $1、2$ 堆合并，新堆数目为 $3$，耗费体力为 $3$。

接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 $12$，耗费体力为 $12$。

所以达达总共耗费体力$=3+12=15$。

可以证明 $15$ 为最小的体力耗费值。

输入格式

输入包括两行，第一行是一个整数 $n$，表示果子的种类数。

第二行包含 $n$ 个整数，用空格分隔，第 $i$ 个整数 $a_i$ 是第 $i$ 种果子的数目。

输出格式

输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。

输入数据保证这个值小于 $2^{31}$。

数据范围

$1 \le n \le 10000$,
$1 \le a_i \le 20000$

输入样例：

3 
1 2 9 

输出样例：

15 

算法分析

因为每次合并消耗的体力等于两堆果子的重量之和, 所以最终消耗的体力总和就是每堆果子的重量乘它参与合并的次数。这恰好对应一个二叉 Huffman 树问题, 果子堆的重量就是叶子节点的权值, 参与合并的次数就是叶子到根的距离。

建立一个小根堆, 揷入所有果子堆的重量。不断取出堆中最小的两个值, 把它们的 和揷入堆, 同时累加到答案中。直至最后堆的大小为 1 时, 输出答案即可。

//Author:XuHt
#include <queue>
#include <cstdio>
#include <iostream>
using namespace std;
priority_queue<int> q;

int main() {
	int n, a;
	cin >> n;
	while (n--) {
		scanf("%d", &a);
		q.push(-a);
	}
	int ans = 0;
	while (q.size() != 1) {
		int x = -q.top();
		q.pop();
		int y = -q.top();
		q.pop();
		ans += x + y;
		q.push(- x - y);
	}
	cout << ans << endl;
	return 0;
}

Solution

---

149. 荷马史诗

追逐影子的人，自己就是影子。 ——荷马

达达最近迷上了文学。

她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。

但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，达达想通过一种编码方式使得它变得短一些。

一部《荷马史诗》中有 $n$ 种不同的单词，从 $1$ 到 $n$ 进行编号。其中第 $i$ 种单词出现的总次数为 $w_i$。

达达想要用 $k$ 进制串 $s_i$ 来替换第 $i$ 种单词，使得其满足如下要求:

对于任意的 $1≤i,j≤n，i≠j$，都有：$s_i$ 不是 $s_j$ 的前缀。

现在达达想要知道，如何选择 $s_i$，才能使替换以后得到的新的《荷马史诗》长度最小。

在确保总长度最小的情况下，达达还想知道最长的 $s_i$ 的最短长度是多少？

一个字符串被称为 $k$ 进制字符串，当且仅当它的每个字符是 $0$ 到 $k−1$ 之间（包括 $0$ 和 $k−1$）的整数。

字符串 $Str1$ 被称为字符串 $Str2$ 的前缀，当且仅当：存在 $1≤t≤m$，使得 $Str1=Str2[1..t]$。

其中，$m$ 是字符串 $Str2$ 的长度，$Str2[1..t]$ 表示 $Str2$ 的前 $t$ 个字符组成的字符串。

注意:请使用 $64$ 位整数进行输入输出、储存和计算。

输入格式

输入文件的第 $1$ 行包含 $2$ 个正整数 $n,k$，中间用单个空格隔开，表示共有 $n$ 种单词，需要使用 $k$ 进制字符串进行替换。

第 $2 \sim n+1$ 行：第 $i+1$ 行包含 $1$ 个非负整数 $w_i$，表示第 $i$ 种单词的出现次数。

输出格式

输出文件包括 $2$ 行。

第 $1$ 行输出 $1$ 个整数，为《荷马史诗》经过重新编码以后的最短长度。

第 $2$ 行输出 $1$ 个整数，为保证最短总长度的情况下，最长字符串 $s_i$ 的最短长度。

数据范围

$2 \le n \le 100000$,
$2 \le k \le 9$
$1 \le w_i \le 10^{12}$

输入样例：

4 2
1
1
2
2 

输出样例：

12
2 

算法分析

本题所构造的编码方式其实就是 Huffman 编码。我们把单词的出现次数 $w_{1} \sim w_{n}$ 作为 Huffman 树叶子节点的权值, 然后求出 $k$ 叉 Huffman 树。对于 Huffman 树每个节点的 $k$ 个分支, 分别在边上标记字符 $0 \sim k-1$ 。

此时, 如果把这棵 Huffman 树看作一棵 Trie 树, 就得到了使总长度最小的编码方式——单词 $i$ 的编码就是从根节点到叶子节点 $i$ 的路径上各条边的字符相连。一个单 词不是另一个的前缀, 其实就对应着: 在 Trie 树中, 所有单词编码的末尾都在叶子节 点上, 而不在 Trie 树的一个内部节点上。我们恰好满足了这个性质。

本题还要求最长的 $s_{i}$ 长度最短, 我们只需要在求 Huffman 树时, 对于权值相同的节点, 优先考虑当前深度最小 (已合并次数最少) 的进行合并即可。

Solution