近似保序霍夫曼码

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

我给出的输入是一个正整数n其次是n正整数，表示有序字符集中符号的频率（或权重）。第一个目标是构造一棵树，为有序字符集中的每个字符提供近似的保序霍夫曼代码。我们要通过“贪婪地将两者合并”来实现这一目标adjacent权重之和最小的树。”

在作业中，我们看到传统的霍夫曼代码树是通过首先将权重插入优先级队列来构建的。然后，通过使用 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。我可以应用什么逻辑来从这些节点开始？我似乎错过了一些东西，但我无法完全理解它。如果您需要更多信息，请告诉我。如果有不清楚的地方，我可以详细说明或提供整个作业页面。

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