# Huffman tree Python implementation

"""
### General Idea:

Given a set of n character set C.

1. Begin with a set of |C| leaves.
2. Repeatedly using **min-priority** queue Q, keyed on frequencies,
identify the two least-frequent objects to merge together.
3. Until all be merged.

### Input

List of tuple containing frequency and character.

### Output

A tree T, called Huffman tree.
"""

import heapq

class Node(object):
def __init__(self, key, freq, left=None, right=None):
self.key = key
self.freq = freq
self.left = left
self.right = right

def __cmp__(self, other):
return cmp(self.freq, other.freq)

def __str__(self):
return "({0}, {1})".format(self.key, self.freq)

def __repr__(self):
return self.__str__()

def encode(rel_freq):
nodes = create_leaf_nodes(rel_freq)
heapq.heapify(nodes)
root = build_encode_tree(nodes)
#print_tree(root)
return root

def create_leaf_nodes(rel_freq):
return map(lambda (freq, key): Node(key, freq), rel_freq)

def merge(n1, n2):
freq = n1.freq + n2.freq
if n1.freq <= n2.freq:
return Node(n1.key + n2.key, freq, n1, n2)
return Node(n2.key + n1.key, freq, n2, n1)

def build_encode_tree(nodes):
root = nodes[0]
while len(nodes) > 1:
n1 = heapq.heappop(nodes)
n2 = heapq.heappop(nodes)
root = merge(n1, n2)
heapq.heappush(nodes, root)
return root

# ---------------- Helpers --------------------------
def print_tree(root):
for nodes in level_order(root):
for node in nodes:
print node,
print

def level_order(node):
"""Given Binary Tree gives list nodes in each level."""
current_level = [node]
while current_level:
yield current_level
next_level = []
for node in current_level:
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
current_level = next_level

import unittest

class TestHuffmanEncoding(unittest.TestCase):
def test_single_char(self):
rel_freq = [(24, 'A')]
actual = str(encode(rel_freq))
self.assertEqual(actual, "(A, 24)")

def test_valid_encoding(self):
#expected = [('A', '0'), ('B', '100'), ('C', '101'), ('D', '110'), ('E', '111')]
rel_freq = [(24, 'A'), (12, 'B'), (10, 'C'), (8, 'D'), (8, 'E')]
expected = "(AEDCB, 62)"
actual = str(encode(rel_freq))
self.assertEqual(actual, expected)

rel_freq = [(45, 'A'), (13, 'B'), (12, 'C'), (16, 'D'), (9, 'E'), (5, 'F')]
expected = "(ACBFED, 100)"
actual = str(encode(rel_freq))
self.assertEqual(actual, expected)

if __name__ == '__main__':
unittest.main()


### Note:

The code do generate the Huffman tree but I am more interested in finding the encoding of each character, the basic approach what I think is traversing each path from root to leaf such that moving left adds 0 to the path and moving right adds 1. Hopefully I would post the solution soon in another review.

Merging is a thing a node and only a node does, using that function on a non-node is meaningless so include it in the node class:

class Node:
...
def merge(self, other_node):


Now the person that uses your code knows that merge works for nodes and nothing else and the code has more structure.

• Hmm, I am confused with the concept of parametric polymerphism, when to apply this concept? Oct 29 '15 at 14:39
• @CodeYogi i do not mean enforcing type safety, just hinting at the way to use it. Oct 29 '15 at 14:40
• Cool! it seems that I am learning alot, now my code seems to have lot less comments :), but I am still confused about the __repr__ stuff, you gave me some comment in my previous post by it was not clear. Oct 29 '15 at 15:12
• If what if I want to merge objects which behaves like node, why bound my method to just one type? Dec 17 '15 at 8:56
• @CodeYogi You are not bounding yourself Dec 17 '15 at 13:35