给定权值10,7,9,8,5,1,2,4,12,14构造一颗哈夫曼树

### 构建哈夫曼树的过程 为了根据给定的权值 {10, 7, 9, 8, 5, 1, 2, 4, 12, 14} 构造一棵哈夫曼树，可以遵循以下方法： #### 权值排序 首先将这些权值按升序排列，得到新的序列：{1, 2, 4, 5, 7, 8, 9, 10, 12, 14}。 #### 合并最小权重节点 每次选择当前列表中两个最小的权值创建一个新的内部节点，并将其作为这两个节点的父亲节点。该父亲节点的权值等于所选两节点之和。重复此操作直到只剩下一个根节点为止。 具体步骤如下所示: - 取出最小的两个权值 `1` 和 `2` 创建一个新节点，其总权值为 `3`。 - 更新后的集合为 `{3, 4, 5, 7, 8, 9, 10, 12, 14}`。 - 接下来取出 `3` 和 `4` 继续上述过程形成另一个父节点，其权值为 `7`。 - 更新后的集合为 `{5, 7, 7, 8, 9, 10, 12, 14}`。 - 再次取最小的两个数 `5` 和 `7` 形成新的父节点，其权值为 `12`。 - 更新后的集合为 `{7, 8, 9, 10, 12, 12, 14}`。 - 下一步是处理 `7` 和 `8` ，生成的新节点拥有 `15` 的权值。 - 更新后的集合为 `{9, 10, 12, 12, 14, 15}`。 - 处理 `9` 和 `10` 得到权值为 `19` 的新节点。 - 更新后的集合为 `{12, 12, 14, 15, 19}`。 - 对于剩下的五个元素中的前两位 `12` 和 `12` 进行组合，获得了一个具有 `24` 权重的新节点。 - 更新后的集合为 `{14, 15, 19, 24}`。 - 将 `14` 和 `15` 结合起来构成一个更大的子树，它有一个总的权值 `29`。 - 更新后的集合为 `{19, 24, 29}`。 - 把 `19` 和 `24` 放在一起形成了一个新的分支，它的累积权值达到了 `43`。 - 更新后的集合为 `{29, 43}`。 - 最终把最后剩余的两个最大数值 `29` 和 `43` 加在一起完成整个哈夫曼树结构，最终形成的根节点拥有的权值为 `72`[^3]。 ```python from heapq import heappush, heappop, heapify import collections def huffman_tree(frequencies): min_heap = [[weight, [symbol, ""]] for symbol, weight in frequencies.items()] heapify(min_heap) while len(min_heap) > 1: lo = heappop(min_heap) hi = heappop(min_heap) for pair in lo[1:]: pair[1] = '0' + pair[1] for pair in hi[1:]: pair[1] = '1' + pair[1] heappush(min_heap, [lo[0]+hi[0]] + lo[1:] + hi[1:]) return sorted(heappop(min_heap)[1:], key=lambda p: (len(p[-1]), p)) frequencies = dict(zip('abcdefghij', [10, 7, 9, 8, 5, 1, 2, 4, 12, 14])) huff = huffman_tree(collections.Counter(frequencies)) for i in huff: print("{}\t{}".format(i[0],i[1])) ```