近似保序霍夫曼码
我正在为算法和数据结构类工作。 我无法理解给出的指示。 我会尽力解释这个问题。
给出的输入是正整数n，后跟n个正整数，表示有序字符集中符号的频率（或权重）。 第一个目标是构造一个树，该树为有序字符集的每个字符提供近似保持秩序的霍夫曼代码。 我们要通过“贪婪地合并权重最小的两棵相邻树木”来实现这一目标。
在分配中，我们示出了通过首先将权重插入优先级队列来构造传统的霍夫曼代码树。 然后通过使用delmin（）函数从优先级队列中“弹出”根，我可以获得频率最低的两个节点，并将它们合并为一个节点，其左侧和右侧是这两个最低频率节点，其优先级为其子女的优先事项总和。 然后将此合并节点插回到最小堆中。 重复该过程，直到合并了所有输入节点。 我使用大小为2 * n * -1的数组实现了这个，输入节点从0 … n -1开始，然后从n … 2 * n * -1作为合并节点。
我不明白如何贪婪地合并权重最小的两棵相邻树。 我的输入基本上被组织成一个小堆，从那里我必须找到具有最小总和的两个相邻节点并合并它们。 通过相邻，我认为我的教授意味着他们在输入中彼此相邻。
示例输入：
9 1 2 3 3 2 1 1 2 3 然后我的min-heap看起来像这样：
1 / \ 2 1 / \ / \ 2 2 3 1 / \ 3 3
那么，具有最小总和的两个相邻树（或节点）是在输入的末端附近出现的两个连续的1。 我可以应用什么逻辑来启动这些节点？ 我似乎错过了一些东西，但我无法理解它。 如果您需要更多信息，请告诉我们。 如果不清楚，我可以自己详细说明或提供整个作业页面。
我认为这可以通过对传统算法的一个小修改来完成。 不是将单个树存储在优先级队列堆中，而是存储相邻树的对。 然后，在每一步中删除最小对(t1, t2)以及最多两对也包含这些树的对，即(u, t1)和(t2, r) 。 然后将t1和t2合并到一个新树t' ，用更新的权重重新插入堆中的对(u, t')和(t', r)并重复。
你需要弹出两棵树并制作第三棵树。 向左节点连接树用较小的和向右节点连接第二棵树。 把这棵树放到堆里。 从你的例子
从堆弹出2树：
1 1
做树
? / \ ? ?
将较小的树放到左侧节点
min(1, 1) = 1 ? / \ 1 ?
放到右边的节点第二棵树
? / \ 1 1
你做的树有sum =左节点的总和+右节点的总和
2 / \ 1 1
将新树（总和2）放入堆中。
最后你会有一棵树，它是霍夫曼树。