def huffman(freq):
"""Huffman code
:param freq: dictionary with frequencies for each item
:returns: dictionary with binary code string for each item
:complexity: O(n log n)
"""
h = []
for a in freq:
heappush(h, (freq[a], a))
while len(h) > 1:
(fl, l) = heappop(h)
(fr, r) = heappop(h)
heappush(h, (fl + fr, [l, r]))
code = {}
extract(code, h[0][1])
return code
评论列表
文章目录