算法基础算法

模拟哈夫曼建树过程的贪心合并问题

字数统计: 2.6k字   |   阅读时长: 11分
, , ,

摘要: 模拟哈夫曼树建树过程的贪心算法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 贪心-哈夫曼编码 和 k叉哈夫曼树 中，我们分别学习了 2 叉哈夫曼树和 K 叉哈夫曼树。

建树的过程比较重要的是它的贪心策略。很多问题的贪心算法参考了哈夫曼树的这种建树过程，本文就例举一些这样的问题并通过贪心算法解决，涉及到的题目总览如下：

$1 2叉哈夫曼建树

1167. 连接棒材的最低费用

你有一些长度为正整数的棍子。这些长度以数组 sticks 的形式给出， sticks[i] 是 第i个 木棍的长度。

你可以通过支付 x + y 的成本将任意两个长度为 x 和 y 的棍子连接成一个棍子。你必须连接所有的棍子，直到剩下一个棍子。

返回以这种方式将所有给定的棍子连接成一个棍子的 最小成本 。

示例 1：
输入：sticks = [2,4,3]
输出：14
解释：从 sticks = [2,4,3] 开始。

  1. 连接 2 和 3 ，费用为 2 + 3 = 5 。现在 sticks = [5,4]
  2. 连接 5 和 4 ，费用为 5 + 4 = 9 。现在 sticks = [9]
    所有木棍已经连成一根，总费用 5 + 9 = 14

示例 2：
输入：sticks = [1,8,3,5]
输出：30
解释：从 sticks = [1,8,3,5] 开始。

  1. 连接 1 和 3 ，费用为 1 + 3 = 4 。现在 sticks = [4,8,5]
  2. 连接 4 和 5 ，费用为 4 + 5 = 9 。现在 sticks = [9,8]
  3. 连接 9 和 8 ，费用为 9 + 8 = 17 。现在 sticks = [17]
    所有木棍已经连成一根，总费用 4 + 9 + 17 = 30

示例 3：
输入：sticks = [5]
输出：0
解释：只有一根木棍，不必再连接。总费用 0

提示：

1
2
1 <= sticks.length <= 1e4
1 <= sticks[i] <= 1e4

算法：贪心，模拟2叉哈夫曼建树

用类似 2 叉哈夫曼建树的过程维护的合并问题。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int connectSticks(vector<int>& sticks) {
        vector<int> heap(sticks.begin(), sticks.end());
        make_heap(heap.begin(), heap.end(), greater<int>()); // greater 生成小顶堆，默认是大顶堆
        // 访问堆头：heap.back()
        // 出堆：pop_heap(), heap.pop_back()
        // 入堆：heap.push_back(x); push_heap()
        int result = 0;;
        while(heap.size() > 1)
        {
            pop_heap(heap.begin(), heap.end(), greater<int>());
            int num1 = heap.back();
            heap.pop_back();

            pop_heap(heap.begin(), heap.end(), greater<int>());
            int num2 = heap.back();
            heap.pop_back();

            int sum = num1 + num2;
            result += sum;
            heap.push_back(sum);
            push_heap(heap.begin(), heap.end(), greater<int>());
        }
        return result;
    }
};

1199. 建造街区的最短时间

你是个城市规划工作者，手里负责管辖一系列的街区。在这个街区列表中 blocks[i] = t 意味着第 i 个街区需要 t 个单位的时间来建造。

由于一个街区只能由一个工人来完成建造。

所以，一个工人要么需要再召唤一个工人（工人数增加 1）；要么建造完一个街区后回家。这两个决定都需要花费一定的时间。

一个工人再召唤一个工人所花费的时间由整数 split 给出。

注意：如果两个工人同时召唤别的工人，那么他们的行为是并行的，所以时间花费仍然是 split。

最开始的时候只有 一个 工人，请你最后输出建造完所有街区所需要的最少时间。

提示：

1
2
3
1 <= blocks.length <= 1000
1 <= blocks[i] <= 10^5
1 <= split <= 100

示例 1：
输入：blocks = [1], split = 1
输出：1
解释：我们使用 1 个工人在 1 个时间单位内来建完 1 个街区。

示例 2：
输入：blocks = [1,2], split = 5
输出：7
解释：我们用 5 个时间单位将这个工人分裂为 2 个工人，然后指派每个工人分别去建造街区，从而时间花费为 5 + max(1, 2) = 7

示例 3：
输入：blocks = [1,2,3], split = 1
输出：4
解释：
将 1 个工人分裂为 2 个工人，然后指派第一个工人去建造最后一个街区，并将第二个工人分裂为 2 个工人。
然后，用这两个未分派的工人分别去建造前两个街区。
时间花费为 1 + max(3, 1 + max(1, 2)) = 4

算法1: 动态规划

1
2
3
4
5
6
7
8
9
10
blocks 已经升序

状态定义：
dp[i][k] := blocks[1..i] 上，初始 k 个人的最短工时

初始化：dp[i][k] = blocks[i]  (i == k)

状态转移：
dp[i][k] = max(blocks[i], 
               min(split + dp[i - (k - j)][j * 2])), j = min(k, i - k),..,1

注：直接按上面列出的动态规划做，会超时。需要一些剪枝，见后面。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int minBuildTime(vector<int>& blocks, int split) {
        int n = blocks.size();
        blocks.push_back(-1);
        sort(blocks.begin(), blocks.end());
        dp = vector<vector<int>>(n + 1, vector<int>(n + 1, -1));
        return solve(blocks, split, n, 1);
    }

private:
    vector<vector<int>> dp;

    int solve(const vector<int>& blocks, const int split, int i, int k)
    {
        // blocks[1..i] 共 i 个街区，k 个人 k <= i
        if(dp[i][k] != -1)
            return dp[i][k];

        dp[i][k] = blocks[i];
        if(i == k) return dp[i][k];

        // k < i
        // 取 j 个人分裂，k - j 个人干活，同时需要满足 j * 2 + k - j < i
        int minx = INT_MAX / 2;
        for(int j = 1; j <= k && (j * 2 <= i - (k - j)); ++j)
        {
            minx = min(minx, split + solve(blocks, split, i - (k - j), j * 2));
        }
        dp[i][k] = max(dp[i][k], minx);
        return dp[i][k];
    }
};

剪枝

将推导状态的以下代码：

1
2
3
4
5
for(int j = 1; j <= k && (j * 2 <= i - (k - j)); ++j)
{
    minx = min(minx, split + solve(blocks, split, i - (k - j), j * 2));
}
dp[i][k] = max(dp[i][k], minx);

改为下面这样，可以通过了。暂时不清楚原因。

1
2
3
4
5
6
7
8
for(int j = min(k, i - k); j >= 1; j >>= 1)
{
    int tmp = max(split + solve(blocks, split, i - (k - j), j * 2), blocks[i]);
    if(tmp < dp[i][k])
        dp[i][k] = tmp;
    else
        break;
}

算法2: 贪心 — 模拟2叉哈夫曼建树

  • 一个街区：

不需要分裂工人，直接让他去建造街区就好了。花费时间 blocks[0]。

  • 两个街区：

必须先把当前的工人分裂为两个工人，然后让他们分别去建造街区。花费时间 split+max(blocks[0], blocks[1])。

两个街区的情形中，分裂工人的操作，实际上就等价于把这两个街区合并为了一个建造时间 为split+max(blocks[0], blocks[1]) 的新街区。

  • N 个街区：

本题的核心： 考虑对N个街区进行合并。选择任意两个街区i和j进行合并后，得到的“新”街区建造时间为： split+max(blocks[i], blocks[j])。

类似于哈夫曼的思路：让耗时长的街区尽可能少参与到合并中，总是优先挑选两个耗时最小的街区进行合并。

注意合并过程维护的内容 : fa.w = split + max(a[i].w, a[j].w)。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minBuildTime(vector<int>& blocks, int split) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int i: blocks)
            pq.push(i);
        while((int)pq.size() > 1)
        {
            int ai = pq.top();
            pq.pop();
            int aj = pq.top();
            pq.pop();
            int fa = split + max(ai, aj);
            pq.push(fa);
        }
        return pq.top();
    }
};

$2 k叉哈夫曼建树

149. 荷马史诗

一篇文章，有 n 种不同的单词，从 1 到 n 进行编号。其中第 i 种单词出现的总次数为 wi。

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

对于任意的 1 <= i,j <= n，i != j，都有：si 不是 sj 的前缀。

如何选择 si，才能使替换以后得到的新的文章的总长度最小。

确保总长度最小的情况下，最长的 si 的最短长度是多少？

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

算法：贪心，模拟K叉哈夫曼树建树

本题构造的编码方式就是哈夫曼编码。

w1~wn 作为哈夫曼树叶子节点的权，然后求出 k 叉哈夫曼树。对于树上每个节点的 k 个分支，在边上标记字符 0~k-1。

此时如果把这棵哈夫曼树视为 Trie，就得到了使得总长度最小的编码方式：单词 i 的编码就是从根节点到叶子节点 i 的路径上各个边的字符相连。

一个单词不是其它单词的前缀，就对应着：在 Trie 中，所有单词编码的末尾都在叶节点上，而不在 Trie 的内部节点上。

最长的 si 的长度最短: 求 Huffman 树时，对于权值相同的节点，优先考虑当前深度最小的进行合并(深度大的分支后合并使其尽量向上走)。

而如果当前的元素个数不能够造一棵完全 k 叉树，即 (n - 1) % (k - 1) = 0 不成立，添加 m 个权值为 0 的虚节点处理。m = k - ((n - 1) % (k - 1)) - 1。

其中 k 为编码字符集大小，n 为待编码单词个数。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

using ll = long long;

struct Node
{
    ll w;
    ll d;
    Node(ll w, ll d):w(w),d(d){}
};

struct HeapCmp
{
    bool operator()(const Node& node1, const Node& node2) const
    {
        if(node1.w == node2.w)
            return node1.d > node2.d;
        return node1.w > node2.w;
    }
};

int main()
{
    int n, k;
    cin >> n >> k;
    priority_queue<Node, vector<Node>, HeapCmp> pq;
    for(int i = 0; i < n; ++i)
    {
        ll w;
        cin >> w;
        pq.push(Node(w, 0));
    }

    if((n - 1) % (k - 1) != 0)
    {
        int m = k - ((n - 1) % (k - 1)) - 1;
        for(int i = 0; i < m; ++i)
            pq.push(Node(0, 0));
    }
    ll ans = 0;
    while(pq.size() != 1)
    {
        ll d = 0, w = 0;
        for(int j = 0; j < k; ++j)
        {
            Node node = pq.top();
            pq.pop();
            d = max(d, node.d + 1);
            w += node.w;
        }
        pq.push({w, d});
        ans += w;
    }
    cout << ans << endl;
    cout << pq.top().d << endl;
}
Share