Tag: min heap

近似保序霍夫曼码

我正在为算法和数据结构类工作。 我无法理解给出的指示。 我会尽力解释这个问题。 给出的输入是正整数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 […]