我正在做一个算法和数据结构类的作业我无法理解所给的指示。我将尽力解释这个问题。
输入I是一个正整数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从这些节点开始，我可以应用什么逻辑？我好像漏掉了什么东西，但我不能完全领会。如果你需要更多的信息，请告诉我如果有什么不清楚的地方，我可以详细说明自己或者提供整个作业页面。
最佳答案
我认为这可以通过对传统算法的一个小修改来实现。不要将单个树存储在优先级队列堆中，而是存储成对的相邻树。然后，在每个步骤中，删除最小对(t1, t2)以及最多两个也包含这些树的对，即(u, t1)和(t2, r)。然后将t1和t2合并到一个新树t'，使用更新的权重在堆中重新插入对(u, t')和(t', r)，然后重复。