Create a gist now

Instantly share code, notes, and snippets.

@st0le /huffman.py
Last active May 19, 2017

What would you like to do?
Py3
from collections import Counter
from heapq import heapify, heappop, heappush
s = input()
c = Counter(s)
pq = [(c[k], k, None, None) for k in c]
codes = {}
heapify(pq)
while len(pq) > 1:
r = heappop(pq)
l = heappop(pq)
heappush(pq, (l[0] + r[0], l[1] + r[1], l, r))
def buildCodes(parent, code):
if parent:
if len(parent[1]) == 1:
codes[parent[1]] = code
buildCodes(parent[2], code + '0')
buildCodes(parent[3], code + '1')
buildCodes(pq[0], '')
print(codes)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment