Building the Huffman Tree
Chapter Seventy-Six
Syllabus topic Module 2, "Trees: Applications of Tree like Huffman Coding"
Pages 238 to 240 of 411
In one line
Repeatedly take the two least frequent items, join them under a new node whose frequency is their sum, and put it back, until one tree remains.
The algorithm
make a leaf for each character, holding its frequency
put all the leaves in a priority queue, ordered by frequency, smallest first
while more than one item remains:
a = remove the smallest
b = remove the next smallest
make a new node with children a and b and frequency a.freq + b.freq
put it back in the queue
the one remaining item is the root
The insight, and it is worth saying in an answer: the two rarest characters should have the longest codes, so they should be deepest, so they should be joined first. Everything joined later sits above them and therefore has a shorter code.
Worked by hand on AAAAABBBCCD
Frequencies: A 5, B 3, C 2, D 1.
step 1: smallest two are D(1) and C(2). Join: node(3) with children D, C.
queue now: node(3), B(3), A(5)
step 2: smallest two are B(3) and node(3), both 3. The tie is broken by
insertion order, so B comes first. Join: node(6).
queue now: A(5), node(6)
step 3: smallest two are A(5) and node(6). Join: node(11), the root.
The tree:
11
/ .
A(5) 6
/ .
B(3) 3
/ .
D(1) C(2)
Codes, reading 0 for left and 1 for right: A = 0, B = 10, D = 110, C = 111.
Built and run
import heapq
from collections import Counter
class HNode:
__slots__ = ("frequency", "character", "left", "right", "order")
def __init__(self, frequency, character=None, left=None, right=None, order=0):
self.frequency = frequency
self.character = character
self.left = left
self.right = right
self.order = order
def __lt__(self, other):
"""Ties are broken by insertion order, so the build is reproducible."""
if self.frequency != other.frequency:
return self.frequency < other.frequency
return self.order < other.order
def build_huffman(text, trace=False):
counts = Counter(text)
counter = 0
heap = []
for character, frequency in sorted(counts.items()):
heapq.heappush(heap, HNode(frequency, character, order=counter))
counter += 1
if len(heap) == 1: # a text of one distinct character
only = heapq.heappop(heap)
return HNode(only.frequency, None, only, None)
while len(heap) > 1:
a = heapq.heappop(heap)
b = heapq.heappop(heap)
joined = HNode(a.frequency + b.frequency, None, a, b, order=counter)
counter += 1
if trace:
print(" join %-10s and %-10s -> %d"
% (describe(a), describe(b), joined.frequency))
heapq.heappush(heap, joined)
return heap[0]
def describe(node):
if node.character is not None:
name = "space" if node.character == " " else node.character
return "%s(%d)" % (name, node.frequency)
return "node(%d)" % node.frequency
def codes(node, prefix="", table=None):
table = {} if table is None else table
if node is None:
return table
if node.character is not None:
table[node.character] = prefix or "0"
return table
codes(node.left, prefix + "0", table)
codes(node.right, prefix + "1", table)
return table
text = "AAAAABBBCCD"
print("text:", text)
print("frequencies:", dict(sorted(Counter(text).items())))
print()
print("building:")
root = build_huffman(text, trace=True)
print()
table = codes(root)
print("the code table:")
for character in sorted(table):
print(" %s -> %-6s (%d bits, used %d times)"
% (character, table[character], len(table[character]),
Counter(text)[character]))
encoded = "".join(table[c] for c in text)
print()
print("encoded :", encoded)
print("bits :", len(encoded))
print("fixed :", len(text) * 2, "bits at 2 bits per character")Building the Huffman Tree
text: AAAAABBBCCD
frequencies: {'A': 5, 'B': 3, 'C': 2, 'D': 1}
building:
join D(1) and C(2) -> 3
join B(3) and node(3) -> 6
join A(5) and node(6) -> 11
the code table:
A -> 0 (1 bits, used 5 times)
B -> 10 (2 bits, used 3 times)
C -> 111 (3 bits, used 2 times)
D -> 110 (3 bits, used 1 times)
encoded : 00000101010111111110
bits : 20
fixed : 22 bits at 2 bits per characterThe program's build matches the hand working exactly: D and C joined first, then that node with B, then A with the result. The codes are A = 0, B = 11, C = 101, D = 100, and the text takes 20 bits instead of 22.
Why a priority queue
The algorithm asks, repeatedly, for the two smallest items among those remaining, and then puts a new item back.
A plain queue cannot do this: chapter 46 showed it knows only arrival order. Sorting the list each time would work and cost O(n log n) per step. A priority queue does exactly this job, removing the smallest in O(log n) and inserting in O(log n), which is why chapter 78 exists and why the heap of chapter 81 is the structure that implements it.
So the total cost is: n insertions to start, then n - 1 rounds each doing two removals and one insertion, all at O(log n). O(n log n), where n is the number of distinct characters.
The tie-breaking detail
When two items have the same frequency, which is taken first? The algorithm does not say, and different choices give different trees.
The codes differ, but the total number of bits is the same for any valid choice, which is the thing that matters and is worth stating in an answer. This book breaks ties by insertion order so that the build is reproducible and the printed table is stable; an examination answer should say which rule it used.
Quick revision
- Make a leaf per character with its frequency; repeatedly join the two smallest under a new node whose
frequency is their sum; the last remaining node is the root.
- The two rarest characters are joined first, so they end up deepest and get the longest codes.
- Codes are read off the tree: 0 for a left edge, 1 for a right edge, root to leaf.
- The algorithm needs the two smallest repeatedly, which is a priority queue, not a queue.
- Cost O(n log n) in the number of distinct characters.
- Ties may be broken any way; different choices give different trees but the same total bits. State your
Building the Huffman Tree
rule.
- Worked: AAAAABBBCCD gives A = 0, B = 10, D = 110, C = 111, and 20 bits against 22 fixed.
Test yourself
1. State the algorithm. Make a leaf for each character holding its frequency. While more than one item remains, remove the two smallest, join them under a new node whose frequency is their sum, and put it back. The last item is the root.
2. Why are the two least frequent joined first? Because joining puts them one level deeper, and everything joined later sits above them. The rarest characters therefore end up deepest and get the longest codes, which is what we want.
3. Build the tree for A 5, B 3, C 2, D 1 and give the codes. Join D and C into 3; join B with that node into 6, the tie between them broken by insertion order; join A with 6 into 11. Codes: A = 0, B = 10, D = 110, C = 111.
4. Why is a priority queue needed rather than a queue? Because the algorithm repeatedly needs the two smallest frequencies, and a queue can only give the oldest item. Sorting each round would work but would cost more.
5. What is the cost of building the tree? O(n log n), where n is the number of distinct characters: n insertions, then n - 1 rounds of two removals and one insertion, each O(log n).
6. Two characters have equal frequency. Does the choice matter? It changes the tree and the individual codes, but not the total number of bits. Any consistent tie-break is acceptable if stated.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.