c - 近似保序霍夫曼码

Question

我正在为算法和数据结构类(class)布置作业。我无法理解给出的说明。我会尽力解释这个问题。

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

在作业中，我们看到传统的霍夫曼代码树是通过首先将权重插入优先级队列来构建的。然后通过使用 delmin() 函数从优先级队列中“弹出”根，我可以获得频率最低的两个节点并将它们合并为一个节点，其左右为这两个频率最低的节点，其优先级为它的 child 的优先事项的总和。然后将合并后的节点插回到最小堆中。重复该过程，直到所有输入节点都已合并。我已经使用大小为 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

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