2

我正在为算法和数据结构课程分配作业。我无法理解给出的说明。我会尽力解释问题。

给定的输入是一个正整数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。我可以应用什么逻辑从这些节点开始？我似乎错过了一些东西，但我无法完全掌握它。如果您需要更多信息，请告诉我。如果有不清楚的地方，我可以详细说明自己或提供整个作业页面。

4

2 回答 2

2

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

于 2012-10-27T06:35:15.377 回答
0

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

从堆中弹出 2 棵树：

1 1

做树

  ?
 / \
?   ?

将较小的树放在左节点

min(1, 1) = 1

  ?
 / \
1   ?

放入右节点第二棵树

  ?
 / \
1   1

您制作的树总和 = 左节点的总和 + 右节点的总和

  2
 / \
1   1

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

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

于 2012-10-27T06:23:58.593 回答