哈夫曼编码的非树节点形式实现

• 楔子
• 思考过程
• • 于是想自己写一个headq
  • 构建二叉树实在太久了，完全不让看文档，不敢不相信在有限的时间里可以调试成功，于是就想了使用非树的实现方式，就是把手动画的二叉树，从树叶往上补充哈夫曼编码
• 总结

楔子

今日心血来潮参加了某厂家的机试，牛客网上机试，一看只有一题且时间90分钟200分，允许使用本地IDE，就知道肯定几分钟出不来，看题目可喜的是秒懂哈夫曼编码，可悲的是一年半以前学的树图数据结构都忘光了。

思考过程

我知道用优先级队列+树可以实现，可是heapq和二叉树一年多没用了，只知道用numpy和pandas汗颜，于是慌了一逼。

于是想自己写一个headq

反正排序用sort()不用自己写，heapq也好实现，后来怕耗时太多，heapq勉强想起来怎么用，稍微试了一下，用起来没问题

构建二叉树实在太久了，完全不让看文档，不敢不相信在有限的时间里可以调试成功，于是就想了使用非树的实现方式，就是把手动画的二叉树，从树叶往上补充哈夫曼编码

from heapq import * # 输入，转化为list strs = input() strs = [i for i in strs]# 去重 str_single = set(strs)# 按照词频入优先级队列 hq =[] for s in str_single:heappush(hq,(strs.count(s),s))# 初始化明文字典 result = {} for i in str_single:result[i] = ''# 从树叶往上构建哈夫曼编码 while hq:left = heappop(hq)if hq:right = heappop(hq)# 取两个最小词频的节点，单个字母优先在左边if left[0] == right[0]:if len(left[1]) > len(right[1]):left,right = right,left# 左边对应编码加0，非单个单词比如‘cd',那么对应的c和d的哈夫曼编码均需要加0for i in left[1]:result[i] += '0'# 右边对应编码加1for i in right[1]:result[i] += '1'# 把合成节点放入优先队列heappush(hq,(left[0]+right[0],left[1]+right[1]))else:break# 最后结果对应哈夫曼编码是反的，故反转一下 for k,v in result.items():v = [i for i in v]result[k] = ''.join(v[::-1]) # 输出结果 for i in strs:print(''.join(result[i]),end='')

总结

还是好好再复习一下树和图吧，否则连面试机会都没有，汗颜！！

总结

以上是生活随笔为你收集整理的哈夫曼编码的非树节点形式实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。