近似保序霍夫曼码

Question

我正在为算法和数据结构课做作业。我很难理解给出的说明。我会尽力解释这个问题。

我得到的输入是一个正整数 n，后跟 n 个正整数，表示有序字符集中符号的频率（或权重）。第一个目标是构造一个树，为有序字符集的每个字符提供近似的顺序保持霍夫曼代码。我们要通过“贪婪地合并权重最小的两棵相邻树”来实现这一点。

在赋值中，我们看到传统的霍夫曼代码树是通过将权重首先插入到优先级队列中来构造的。然后通过使用 delmin（） 函数从优先级队列中“弹出”根，我可以获取频率最低的两个节点并将它们合并为一个节点，其左右是这两个频率最低的节点，其优先级是其子节点的优先级之和。然后，此合并节点将重新插入到最小堆中。重复该过程，直到所有输入节点都已合并。我使用大小为 2*n*-1 的数组实现了这一点，输入节点从 0...n-1 开始，然后从 n...2*n*-1 是合并的节点。

我不明白我怎么能贪婪地合并权重最小的两棵相邻树。我的输入基本上被组织成一个最小堆，从那里我必须找到两个总和最小的相邻节点并合并它们。通过相邻，我假设我的教授意味着它们在输入中彼此相邻。

输入示例：

9
1
2
3
3
2
1
1
2
3

然后我的最小堆将如下所示：

               1
          /         \
        2            1 
     /     \        /  \
    2       2      3    1
   /  \
  3    3 

具有最小总和的两个相邻的树(或节点)是出现在输入末尾附近的两个连续的1。我可以应用什么逻辑从这些节点入手？我似乎错过了一些东西，但我不能完全掌握它。如果你需要更多的信息，请告诉我。如果有不清楚的地方，我可以详细说明或者提供整个作业页面。

Answer 1

你需要弹出两棵树并制作第三棵树。向它左边的节点加入树，用较小的总和，向右的节点加入第二棵树。把这棵树堆起来。从您的示例

从堆中弹出2棵树：

1 1

使树

  ?
 / \
?   ?

将较小的树放在左侧节点

min(1, 1) = 1

  ?
 / \
1   ?

放在右节点第二棵树

  ?
 / \
1   1

你做的树有sum =左节点和右节点和

  2
 / \
1   1

将新树（总和 2）放入堆中。

最后你会有一棵树，它是霍夫曼树。

Answer 2

我认为这可以通过对传统算法的小修改来完成。与其在优先级队列堆中存储单个树，不如存储相邻树对。然后，在每一步中，您都删除最小对（t1， t2）以及最多两对也包含这些树的对，即（u， t1）和（t2， r）。然后将t1和t2合并到新树t'中，用更新的权重在堆中重新插入对（u， t'）和（t'， r）并重复。