不使用优先级队列的huffman树
不使用优先级队列的huffman树
提问于 2022-11-16 16:29:42
对于我的项目，我必须创建一个huffman树项目，但我的讲师说我不能使用优先级队列来构建它？但我不知道该怎么做。还有其他方法可以不用优先级队列来创建huffman树吗？
回答 1
Stack Overflow用户
发布于 2022-11-17 12:24:13
在实践中，有一个经常被用来建造赫夫曼树的技巧：
- 创建一个包含概率的符号列表，并按升序排序。
- 为组合符号创建一个初始空列表。在我们工作的时候，这个问题还会得到解决。
- 虽然列表中有多个符号：
1. Remove the two smallest symbols from the beginnings of two lists
2. Combine them and add them to the end of the combined list. Because the new symbol has a higher combined probability than any combined symbol created before, this list remains sorted.在初始排序之后，最小的概率符号总是两个列表中的第一个，因此不需要优先级队列或搜索就可以找到它。
这种技巧相当聪明，而且你的讲师也不会指望你自己去想它，所以它很可能是在课堂上教或引用的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/74464025
复制相关文章
相似问题
腾讯云开发者
