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.

1. 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 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_e

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.

StackExchange Code Review Q#109080, answer score: 4