The Huffman coding idea with heapq

Why this lesson matters

Huffman coding is the classic greedy algorithm that uses a heap. Its idea sits inside file compression. The ZIP and gzip formats use a method called DEFLATE, which includes Huffman codes, and the JPEG image format also uses Huffman coding. It is also a favourite interview question, because it ties together three things you have already met: greedy choices, trees and heaps.

By the end of this lesson you will be able to explain why common letters should get short codes, state the prefix-free rule, build a Huffman tree by hand, compute the size of a compressed message with a shortcut, and write Python that builds the codes, encodes a message and decodes it again.

The problem: bits are the only currency

A computer stores everything as bits. A bit is a single digit that is either 0 or 1. Text is stored as a list of codes, and each code is a few bits long. The question is: how many bits does each letter need?

Suppose your message uses six different letters. You cannot give each letter a 1-bit code, because there are only two 1-bit codes, 0 and 1. With 2-bit codes you have four options, which is still not enough. With 3-bit codes you have eight options, which covers six letters. So a plain, fixed-length scheme uses 3 bits for every letter. A message of 100 letters then takes 100 * 3 = 300 bits.

But letters are not equally common. In English text, e appears far more often than z. If the common letters get short codes and the rare letters get long codes, the total drops. Think of Morse code, where the most common letter, e, is a single dot, while rare letters use four or more symbols. The same idea, applied with a rule that guarantees correctness, is Huffman coding.

The catch: codes must not be confused

Suppose you give a the code 0 and b the code 01. Now a message that contains the bits 01 is ambiguous. It could be b, or it could be a followed by a 1, which might be the start of another code. A decoder cannot know where one letter stops and the next starts.

The fix is the prefix-free rule. A code is prefix-free when no code is the beginning of another code. The codes a = 0, b = 10 and c = 11 are prefix-free, because 0 is not the start of 10 or 11, and 10 is not the start of 11. A decoder can read bits from left to right and output a letter as soon as the bits match a code, with no spaces needed.

A prefix is the beginning of a string. The word pre is the prefix of prefix. In this lesson, a code that is the prefix of another code is a problem, because the decoder would stop too early.

The code tree

Prefix-free codes fit neatly in a tree. Start at the root, the top node. Each step down goes left for a 0 and right for a 1. A node with no children is a leaf, and each leaf holds one letter. The code of a letter is the list of steps from the root to its leaf.

Here is the tree for the codes a = 0, b = 10, c = 11. The root has two children. The left child is the leaf a. The right child has two leaves, b and c.

          root
         /    \
       0/      \1
       a      (node)
             /     \
           0/       \1
            b        c

Decoding is a walk down this tree. Read a bit, move left or right, and when you reach a leaf, output its letter and return to the root. This is why the prefix-free rule matters. A leaf is always the end of a letter, because no letter's code continues past a leaf.

Huffman coding is a rule for building this tree so that frequent letters end up near the root and rare letters end up deep in the tree.

An everyday analogy

Think of a city with a central office. Staff who visit the office every day should have a short route to it. Staff who visit once a year can have a long route, because the extra steps cost little overall. The total time spent walking is the sum over everyone of (how often they visit) times (the length of their route).

A Huffman tree works the same way. Each letter's cost is its frequency times its code length. The total cost is the total encoded size. Short routes go to frequent letters, and the greedy rule decides the routes.

The greedy rule

Huffman's rule is this. Take the two items with the smallest frequencies. Join them under a new parent node whose frequency is their sum. Put the new node back among the items. Repeat until only one item is left. That last item is the root.

In steps:

1. Make one leaf for each symbol, holding the symbol and its frequency. Put all the leaves in a collection that always gives back the smallest frequency first. That is a min-heap, covered in the next section.
2. Remove the two smallest items. Make a new node whose children are these two. Its frequency is the sum of their frequencies.
3. Put the new node back into the collection.
4. Repeat steps 2 and 3 until one node is left. It is the root of the tree.
5. Walk the tree. Each left edge adds a 0 to the code, and each right edge adds a 1. The code for each leaf is the list of bits on the path to it.

Why merge the smallest two? The rarest symbols should be merged first. Merging puts them deeper in the tree, which gives them longer codes. The most common symbols are merged last, so they stay close to the root. Lesson 4 gives the exchange argument that proves this is the best you can do with prefix-free codes.

Min-heaps and heapq

To run the rule quickly, you need a data structure that gives back the smallest item in a short time. That structure is a heap. A min-heap keeps the smallest item at the top. You can add an item, and you can remove the smallest one, each in O(log n) time.

Python provides a min-heap in the standard library module heapq. A module is a file of ready-made code that you load with import. Two functions do the work. heapq.heappush(heap, item) adds an item. heapq.heappop(heap) removes the smallest item and returns it. The heap is an ordinary Python list, and heapq keeps the list in heap order.

heapq compares items with <. Numbers compare by value. For our nodes we need a custom order, so we push a tuple such as (frequency, symbol, node). A tuple compares item by item. The first item decides, and the later items break ties. If you know Java, heapq plays the role of PriorityQueue, but the order comes from the items you push, not from a comparator object.

The visualizer below shows a heap. Watch how each new item sifts up to its place, and how removing the top item moves the last item to the top and sifts it down.

The heap does not keep all items in sorted order. It keeps only the smallest item at the top, with a weaker order below. That is enough for Huffman coding, because each step needs only the two smallest items.

Worked example: six symbols by hand

Here are six symbols and their frequencies, which is how many times each symbol appears in a message of 100 symbols:

Step 1: put the six leaves in the heap. The smallest is a with 5.

Step 2: remove the two smallest, a (5) and b (9). Make a node 14 with them as children. Put 14 back. The heap now holds c (12), d (13), e (16), 14 and f (45).

Step 3: remove c (12) and d (13). Make a node 25. Put it back.

Step 4: remove the two smallest, 14 and e (16). Make a node 30. Put it back. The heap now holds 25, 30 and f (45).

Step 5: remove 25 and 30. Make a node 55. Put it back. The heap now holds 45 (f) and 55.

Step 6: remove f (45) and 55. Make the root 100. The heap is empty, and the tree is complete.

The table below records the five merges. Each row is one greedy choice.

Read the root's left and right children from the merges. In merge 5, f is taken first because it is smaller, so f becomes the left child and gets the code starting with 0. The node 55 is the right child, so its codes start with 1.

Following the same rule gives these codes: f is 0, c is 100, d is 101, a is 1100, b is 1101, and e is 111. Check that no code is the beginning of another. The codes starting with 1 split into 100, 101, 1100, 1101 and 111, and none of them is a prefix of another, so the set is prefix-free.

The diagram below shows the same tree with the frequencies in the nodes and the bits on the edges.

Huffman tree for frequencies a 5, b 9, c 12, d 13, e 16, f 45: f is 0, c is 100, d is 101, a is 1100, b is 1101, e is 111

The total size, computed two ways

The encoded size of the message is each symbol's frequency times its code length, added up over all symbols:

• f: 45 times 1 bit = 45
• c: 12 times 3 bits = 36
• d: 13 times 3 bits = 39
• a: 5 times 4 bits = 20
• b: 9 times 4 bits = 36
• e: 16 times 3 bits = 48

The total is 45 + 36 + 39 + 20 + 36 + 48 = 224 bits. A fixed-length code of 3 bits per symbol needs 100 * 3 = 300 bits. Huffman saves 76 bits, a little over a quarter.

There is a shortcut. The total also equals the sum of the merge weights: 14 + 25 + 30 + 55 + 100 = 224. Why? Each merge adds one bit to every symbol below that merge. So the weight of a merged node counts the bits it adds to the message. Adding all the merge weights gives the total number of bits. This shortcut is the basis of the cost-only program later in this lesson, which never builds the tree at all.

Worked example: a skewed alphabet

The six-symbol example has many frequencies, so the saving looks modest. A more skewed alphabet shows the effect clearly. Take four symbols with frequencies 1, 2, 4 and 8, which add up to 15 symbols in the message.

Step 1: the two smallest are 1 and 2. Merge them into a node of 3. The heap holds 3, 4 and 8.

Step 2: the two smallest are 3 and 4. Merge them into a node of 7. The heap holds 7 and 8.

Step 3: merge 7 and 8 into the root, 15.

The root's left child is the node 7, which has the children 3 and 4. The node 3 has the leaves 1 and 2. Reading the edges gives the codes. The symbol with frequency 8 is the right child of the root, so its code is 1, one bit. The symbol with frequency 4 is code 01. The symbol with frequency 2 is code 001. The symbol with frequency 1 is code 000. No code starts another, so the set is prefix-free.

The encoded size is 8 times 1, plus 4 times 2, plus 2 times 3, plus 1 times 3. That is 8 + 8 + 6 + 3 = 25 bits. A fixed two-bit code for four symbols would need 15 times 2 = 30 bits. Huffman saves 5 bits, and the saving comes from the most frequent symbol getting a one-bit code. The merge weights agree: 3 + 7 + 15 = 25.

Notice the pattern. The most common symbol gets the shortest code, and each rarer symbol gets a code one bit longer. That pattern appears whenever frequencies double, which is why skewed data compresses so well. When every frequency is the same, the pattern disappears, and the saving disappears with it.

Program: build the codes from a table

The first program reads the symbols and their frequencies from the Input box. It builds the tree with a heap, walks the tree to assign codes, and prints each symbol with its code and the total number of bits.

It uses a small class called Node. A class is a blueprint for objects. Each node has a symbol, which matters only for leaves, a frequency, and two child links. The line self.left = left stores a child. None is Python's word for no value, and a leaf has None in its child links. Module 16 covers classes in full. For now, Node(...) creates one node, and node.is_leaf() asks whether it has children.

import heapq
import sys
 
 
class Node:
    def __init__(self, symbol, freq, left=None, right=None):
        self.symbol = symbol      # meaningful only for leaves
        self.freq = freq
        self.left = left
        self.right = right
 
    def is_leaf(self):
        return self.left is None
 
 
def join(left, right):
    # An internal node: its symbol only breaks ties, so the output is the same every run.
    return Node(min(left.symbol, right.symbol), left.freq + right.freq, left, right)
 
 
codes = {}
 
 
def assign(node, path):
    if node.is_leaf():
        codes[node.symbol] = path
        return
    assign(node.left, path + "0")
    assign(node.right, path + "1")
 
 
def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    freq_of = {}
    heap = []
    pos = 1
    for _ in range(n):
        symbol = data[pos]
        freq = int(data[pos + 1])
        pos += 2
        freq_of[symbol] = freq
        # Tuples compare item by item: frequency first, then symbol.
        heapq.heappush(heap, (freq, symbol, Node(symbol, freq)))
 
    while len(heap) > 1:
        _, _, a = heapq.heappop(heap)    # smallest
        _, _, b = heapq.heappop(heap)    # second smallest
        parent = join(a, b)
        heapq.heappush(heap, (parent.freq, parent.symbol, parent))
 
    _, _, root = heapq.heappop(heap)
    assign(root, "")
 
    bits = 0
    for symbol in sorted(codes):
        code = codes[symbol]
        bits += freq_of[symbol] * len(code)
        print(f"{symbol} freq {freq_of[symbol]} code {code}")
    print(f"total bits: {bits}")
 
 
if __name__ == "__main__":
    main()

Input to type into the Input box:

6
a 5
b 9
c 12
d 13
e 16
f 45

Output:

a freq 5 code 1100
b freq 9 code 1101
c freq 12 code 100
d freq 13 code 101
e freq 16 code 111
f freq 45 code 0
total bits: 224

The output matches the hand calculation exactly. Read the program in parts. The Node class stores the fields. The join function makes an internal node from two existing nodes. It adds their frequencies, and it gives the new node the smaller of the two child symbols. That symbol is not used for coding. It is only a tie-breaker, so that two nodes with the same frequency always come out in the same order.

The heap holds tuples of the form (frequency, symbol, node). The tuple compares frequencies first. When they are equal, it compares the symbols. The node is the third item, and Python does not compare it in practice. Each symbol belongs to exactly one item in the heap, so two items never match on both frequency and symbol. This matters, because when two frequencies tie, the codes can differ between programs that break the tie differently. A fixed tie-break makes the output reproducible, so you can check it by hand.

The assign function is a recursive walk down the tree. It is a short function that calls itself on the left child with 0 added to the path, and on the right child with 1 added. When it reaches a leaf, it records the path as that leaf's code. The sequence of calls is the same as a tree traversal, which the next visualizer shows on a small tree.

Watch the order in which the nodes are visited. The walk goes all the way down the left side first, records a code at the first leaf, then comes back up and goes down the next branch. That is the same depth-first order used by assign.

The final loop adds up the bits. For each symbol it multiplies the frequency by the code length, and it prints one line per symbol. The loop goes over sorted(codes), so the symbols always come out in alphabetical order.

What happens inside the heap

A heap is a binary tree stored in a list. The item at the top is the smallest. The children of the item at position i are at positions 2i + 1 and 2i + 2. When you add an item, heappush puts it at the end and moves it up while it is smaller than its parent. When you remove the top item, heappop moves the last item to the top and moves it down until both of its children are larger.

The steps above are the textbook version of the idea. CPython's heapq moves the empty top spot down to a leaf first and then sifts the last item back up. This takes fewer comparisons on average. The positions can differ from a textbook trace, but the top is always the smallest.

Each move swaps one pair of items, and the number of moves is at most the height of the tree, which is about log n. So each heappush or heappop takes O(log n) time. Building the whole Huffman tree needs n - 1 merges, and each merge does two pops and one push. The total time is O(n log n).

This explains why the heap is a good fit. You never need the full list in sorted order. You need only the two smallest items at each step, and a heap gives them quickly.

Program: merge steps and the total cost

Sometimes you only need the total number of bits, not the codes themselves. The next program skips the tree and works with a heap of plain numbers. It prints each merge, so you can match it against the table in the worked example. The function heapq.heapify turns a list into a heap in one pass, so the program does not push the numbers one at a time.

import heapq
import sys
 
 
def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    heap = [int(x) for x in data[1:1 + n]]
    heapq.heapify(heap)
 
    total = 0
    step = 1
    while len(heap) > 1:
        x = heapq.heappop(heap)      # smallest
        y = heapq.heappop(heap)      # second smallest
        merged = x + y
        total += merged
        print(f"step {step}: {x} + {y} = {merged}")
        step += 1
        heapq.heappush(heap, merged)
    print(f"total bits: {total}")
 
 
if __name__ == "__main__":
    main()

Input to type into the Input box:

6
5 9 12 13 16 45

Output:

step 1: 5 + 9 = 14
step 2: 12 + 13 = 25
step 3: 14 + 16 = 30
step 4: 25 + 30 = 55
step 5: 45 + 55 = 100
total bits: 224

The five merges are the same as the table in the worked example, and the total is the sum of the merged values, 14 + 25 + 30 + 55 + 100. This program is the cost shortcut in code. It is shorter than the tree version, and it is correct for the cost. Use it when the problem asks for the size only. Use the tree version when the problem asks for the codes.

Note one detail. A Python int has no fixed size. It grows to hold any number, so total cannot wrap around to a wrong value. Languages with fixed-size integers, such as C and Java, need a wider type for large sums. NumPy arrays of integers have a fixed size too, and they can overflow silently. The plain Python version of this program prints the exact total for any input size.

Encode and decode: a round trip

Encoding a message means replacing each letter with its code. Decoding means walking the tree with the bits. A good test is a round trip: encode a message, decode the result, and check that you get the original message back. The next program does both, using the same code table as before.

import heapq
import sys
 
 
class Node:
    def __init__(self, symbol, freq, left=None, right=None):
        self.symbol = symbol
        self.freq = freq
        self.left = left
        self.right = right
 
    def is_leaf(self):
        return self.left is None
 
 
def join(left, right):
    return Node(min(left.symbol, right.symbol), left.freq + right.freq, left, right)
 
 
codes = {}
 
 
def assign(node, path):
    if node.is_leaf():
        codes[node.symbol] = path or "0"
        return
    assign(node.left, path + "0")
    assign(node.right, path + "1")
 
 
def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    heap = []
    pos = 1
    for _ in range(n):
        symbol = data[pos]
        freq = int(data[pos + 1])
        pos += 2
        heapq.heappush(heap, (freq, symbol, Node(symbol, freq)))
    while len(heap) > 1:
        _, _, a = heapq.heappop(heap)
        _, _, b = heapq.heappop(heap)
        parent = join(a, b)
        heapq.heappush(heap, (parent.freq, parent.symbol, parent))
    _, _, root = heapq.heappop(heap)
    assign(root, "")
 
    # Encode: replace each letter by its code.
    message = data[pos]
    bits = "".join(codes[c] for c in message)
    print("encoded: " + bits)
 
    # Decode: follow the bits from the root. At a leaf, output the letter and start again.
    decoded = []
    node = root
    for bit in bits:
        node = node.left if bit == "0" else node.right
        if node.is_leaf():
            decoded.append(node.symbol)
            node = root
    print("decoded: " + "".join(decoded))
 
 
if __name__ == "__main__":
    main()

Input to type into the Input box (the six symbol lines, then the message on its own line):

6
a 5
b 9
c 12
d 13
e 16
f 45
cafe

Output:

encoded: 10011000111
decoded: cafe

Check the encoding by hand. The letter c is 100, a is 1100, f is 0, and e is 111. Joined in order, that gives 100 then 1100 then 0 then 111, which is 10011000111. The decoder reads the bits from the root. It goes 1, 0, 0, which reaches the leaf c, so it outputs c and returns to the root. Then 1, 1, 0, 0 reaches a. Then 0 reaches f. Then 1, 1, 1 reaches e. The output is cafe.

The decoder never needs to know where a letter ends. The prefix-free rule guarantees that a leaf is always the end of one letter. This is the payoff for the rule from the earlier section.

The decode loop keeps the walk in one variable, node. Each bit moves node to the left or right child. When node reaches a leaf, the program appends the letter and resets node to the root. The variable node is the position in the tree, and it always starts from the root for the next letter.

In a real file, the code table is saved with the compressed data. Otherwise the decoder could not rebuild the tree. Formats such as DEFLATE store the code lengths, and both sides rebuild the same codes from those lengths.

Edge case: one symbol

What happens when the message has only one kind of symbol? Consider a file of a hundred x letters. The heap holds one leaf, and the while loop never runs. The root is the leaf itself. Its code is the empty string, because the path from the root to the root has no steps. A code of zero bits means the encoded message has zero length, so the message cannot be recovered.

The next program shows what goes wrong. It is written with a bug on purpose. It builds a tree for one symbol, and then encodes a message of four x letters. Run it and look at the output before you read on.

import heapq
import sys
 
 
class Node:
    def __init__(self, symbol, freq, left=None, right=None):
        self.symbol = symbol
        self.freq = freq
        self.left = left
        self.right = right
 
    def is_leaf(self):
        return self.left is None
 
 
def join(left, right):
    return Node(min(left.symbol, right.symbol), left.freq + right.freq, left, right)
 
 
codes = {}
 
 
# Buggy on purpose: the code of a single symbol stays an empty string.
def assign(node, path):
    if node.is_leaf():
        codes[node.symbol] = path
        return
    assign(node.left, path + "0")
    assign(node.right, path + "1")
 
 
def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    heap = []
    pos = 1
    for _ in range(n):
        symbol = data[pos]
        freq = int(data[pos + 1])
        pos += 2
        heapq.heappush(heap, (freq, symbol, Node(symbol, freq)))
    while len(heap) > 1:
        _, _, a = heapq.heappop(heap)
        _, _, b = heapq.heappop(heap)
        parent = join(a, b)
        heapq.heappush(heap, (parent.freq, parent.symbol, parent))
    _, _, root = heapq.heappop(heap)
    assign(root, "")
 
    message = data[pos]
    bits = "".join(codes[c] for c in message)
    print(f"code of x: [{codes['x']}]")
    print(f"encoded {message}: [{bits}] ({len(bits)} bits)")
 
 
if __name__ == "__main__":
    main()

Input to type into the Input box:

1
x 5
xxxx

Output:

code of x: []
encoded xxxx: [] (0 bits)

The program does not crash, and that is the danger. It prints zero bits for four letters, which is wrong, and nothing in the output warns you. The fix is one line. When the path is empty, which only happens for a single leaf, give the symbol the code 0. The fixed line is codes[node.symbol] = path or "0". The round-trip program above already uses that form. With the fix, code of x: [0] and encoded xxxx: [0000] (4 bits).

Always test the one-symbol case. Interviewers ask about it, and it is the case most likely to slip through when you only test with the example from the textbook.

Where Huffman does and does not help

Huffman coding saves bits when the frequencies are unequal. If all six symbols appear equally often, the average code is about 2.67 bits, against 3 for a fixed scheme, a small saving. With four equal frequencies, Huffman gives 2-bit codes, the same as a fixed scheme, and saves nothing. The savings come from skew: the more uneven the frequencies, the more Huffman wins.

Huffman is also a lossless method. Lossless means that decoding gives back exactly the original message, bit for bit. JPEG images use Huffman coding inside a lossy pipeline, where some detail is removed first, but the Huffman step itself is lossless. Keep the two ideas separate in your head when you discuss compression.

Why the greedy merge gives the smallest total

It is worth knowing why this rule is optimal, not just that it works on the examples. You can see the core of the argument with the exchange idea from lesson 4. Suppose two symbols have the smallest frequencies in the whole message. In an optimal code, the two rarest symbols can be made siblings at the deepest level of the tree. If they are not siblings, you can swap them with the symbols that are, and the total cost does not go up, because the rare symbols take the longest codes either way.

Once the two rarest symbols are siblings, you can replace them with one combined symbol whose frequency is their sum. The rest of the problem is the same problem on one fewer symbol, so the same argument applies again. This is why each greedy merge is safe. The merge does not have to be undone later, because an optimal code always has this shape.

You do not need to write this proof in an interview. It is enough to say that the two rarest symbols can be siblings in an optimal tree, and then merge them. Knowing the reason lets you explain the choice without guessing.

Complexity

Let n be the number of distinct symbols.

• Building the tree: n - 1 merges. Each merge does two pops and one push, and each one takes O(log n). The total is O(n log n).
• Computing the cost only: the same heap work, O(n log n), with no tree.
• Encoding a message of length L: O(L) lookups in the code table, plus the length of the output.
• Decoding: O(B), where B is the number of bits, since each bit moves one step in the tree.
• Space: O(n) for the tree and the code table.

When you explain this in an interview, say the heap work first and the merge count second. Then say that decoding is linear in the number of bits.

Common mistakes and their real messages

Merging the two largest instead of the two smallest. The tree is still valid, but the total is larger. The cost on the six-symbol example would be 416, not 224. The fix is to pop from a min-heap, which gives the smallest first. Check the first merge by hand: it must join the two smallest frequencies.

Expecting the largest item from heappop. heapq is a min-heap only. heappop returns the smallest item, and there is no option for a max-heap. To get the largest first, push negated numbers and negate them again after popping. Print the first two pops to check the order. Python gives no error for this mistake.

Forgetting the prefix-free rule when inventing codes by hand. If you write a = 0, b = 01, c = 1, the decoder cannot tell 01 from 0 followed by 1. A Huffman tree always avoids this, but a hand-made table does not.

Pushing nodes into the heap without a sort key. Each heap item is compared with < when the heap works. A Node object has no <, so Python raises an error as soon as the heap needs to compare two of them:

TypeError: '<' not supported between instances of 'Node' and 'Node'

The fix is the tuple (frequency, symbol, node), as the programs above do. The first two items decide the order, so the node is not compared. Another fix is to define a method named __lt__ on the class, which tells Python how one node is less than another. Module 16 covers that method.

A None child in the decode walk. If the decoder follows a left or right link that was never set, that link is None. Calling a method on None makes Python raise an AttributeError. The message below came from a small program that asked for root.left on a node with no children and then called is_leaf() on the result:

AttributeError: 'NoneType' object has no attribute 'is_leaf'

Read the last line first. It names the type of the value, NoneType, which is the type of None, and the attribute that was missing, is_leaf. The lines above it give the file, the line number and the code that failed. For a Huffman decoder, the usual cause is a bit string that does not match the tree, or a tree built from the wrong input. Check the code table first.

Ignoring the one-symbol case. As shown above, a single symbol gets an empty code and the output is wrong. Give the single symbol the code 0.

A very skewed tree and the recursion limit. assign calls itself once per level of the tree. Python stops a chain of calls at a fixed depth, which is 1000 by default. You can read the limit with sys.getrecursionlimit(). A tree is deep when its frequencies grow fast, for example 1, 2, 4, 8 and so on. A program that builds such a tree with 1100 symbols fails with this message, and the traceback above it shows the assign line many times:

RecursionError: maximum recursion depth exceeded

Real text frequencies do not produce trees this deep. The fix for an input that does is a loop with an explicit list of nodes to visit, which does not use the call stack. Raising the limit with sys.setrecursionlimit also works for moderate depths, but a very large limit can crash the interpreter.

Debugging walkthrough: checking the merges

When the cost is wrong, print the merges, exactly as the second program does. Check each line. The two numbers on the left of = must be the two smallest values left at that step. If a larger number appears on the left, the heap order or the tuple order is wrong.

Then check the sum. The total must equal the sum of all the merged values. If it does not, a merge was counted twice, or a merged node was not pushed back into the heap.

Finally, check the codes against the prefix-free rule. Read each code, and check that it is not the beginning of any other code. A code that is the beginning of another means the tree was not built as a proper tree. Each leaf must be a leaf, and each internal node must have exactly two children.

Interview questions you should be ready for

1. What does Huffman coding minimise? The total number of bits, which is the sum over symbols of frequency times code length. The tree gives the smallest total among all prefix-free codes.
2. Why merge the two smallest first? Merging puts the merged nodes deepest in the tree, so the rare symbols get the longest codes. Common symbols stay near the root.
3. Why must the codes be prefix-free? So the decoder knows where each letter ends, without spaces or extra markers.
4. What is the running time? O(n log n), from n - 1 merges, each doing heap work of O(log n).
5. What happens with equal frequencies? The tree is not unique, but every tree the rule builds has the same total cost. Different tie-breaks give different codes with the same size.
6. What about a single symbol? It needs at least one bit. Assign the code 0 to avoid an empty code.

Real-world uses

Huffman coding is part of many compression formats. DEFLATE, which underlies ZIP and gzip, uses Huffman codes to shrink the output of an earlier stage that finds repeated text. JPEG, the common image format, uses Huffman tables for the coefficients of each block. Some text formats and older fax standards use the same idea with fixed tables.

The method also appears as a teaching example in data compression courses, because it shows how a simple greedy rule, backed by a heap, can give an optimal result. That is why it is a common interview topic.

Practice

1. Find the Huffman total for frequencies 1, 1, 2, 3. Write each merge, then add the merge weights. Check your answer with the cost program.

Show the answer

Merge 1 and 1 to make 2. The heap then holds 2, 2, 3. Merge 2 and 2 to make 4. The heap holds 3 and 4. Merge 3 and 4 to make 7. The merge weights are 2, 4 and 7, which add to 13. The cost program prints 13.

2. Why must a prefix-free code be used? Give a short example of two codes that break the decoder.

Show the answer

If one code is 0 and another is 01, a decoder reading 01 cannot tell whether it means one letter or two. The decoder needs to know where each letter ends, and a prefix-free set guarantees that a code is never the start of another code.

3. What happens when there is only one symbol? Explain why its code must have at least one bit.

Show the answer

With one symbol, the tree is a single leaf. Its code is the empty path, which has zero bits, so the encoded message would be empty. The symbol needs at least one bit, so give it the code 0.

4. Build the Huffman tree for frequencies 1, 2, 4, 8 by hand. Write the codes for each symbol, and check that they are prefix-free.

Show the answer

Merge 1 and 2 to make 3. The heap holds 3, 4, 8. Merge 3 and 4 to make 7. The heap holds 7 and 8. Merge 7 and 8 to make the root, 15. Going left gives 0 and going right gives 1. The node 8 is the right child of the root, so its code is 1. The node 7 is the left child, and it splits into the node 3 (code 00) and the leaf 4 (code 01). The node 3 splits again into the leaf 1 (code 000) and the leaf 2 (code 001). The codes are 8 is 1, 4 is 01, 2 is 001, and 1 is 000. They are prefix-free, because none is the start of another. The total cost is 3 + 7 + 15 = 25, which matches 1 times 3 + 2 times 3 + 4 times 2 + 8 times 1 = 25.

5. For frequencies 4, 4, 4, 4, compute the total cost. Then compute the cost with a fixed 2-bit code. Which is smaller, and why?

Show the answer

Each merge adds 4 + 4 = 8, then 8 + 8 = 16 in the second merge, and the total is 8 + 8 + 16 = 32. The fixed 2-bit code gives 4 times 4 times 2 = 32 bits as well. They are equal, because all frequencies are equal, so Huffman gives no gain.

6. Change the cost program so it handles 20000 symbols that each have frequency one billion. What is the total? Would the total fit in a 64-bit integer?

Show the answer

Replace the input reading with heap = [10**9] * 20000 and heapq.heapify(heap), then run the same loop. The total is 287232000000000, which is about 2.9 times 10^14. It fits in a 64-bit integer, which holds up to 9223372036854775807, and it does not fit in a 32-bit integer, which holds up to 2147483647. The Python version needs no special type, because a Python int grows to hold any size.

7. Given the codes a = 0, b = 10, c = 110, d = 111, decode the bits 0101101110.

Show the answer

Read the bits. 0 is a. Then 10 is b. Then 110 is c. Then 111 is d. Then 0 is a. The output is abcda.

8. Two merges produce node weights 14 and 25. What is the next merge if the only other item in the heap is 30? Show the heap contents before and after.

Show the answer

The heap holds 14, 25 and 30 before the merge. The two smallest are 14 and 25, so the next merge is 14 plus 25, giving 39. After the merge the heap holds 30 and 39.

9. Explain in your own words why the encoded size of a message equals the sum of the merge weights. Use one symbol as an example.

Show the answer

Take symbol a (frequency 5) from the six-symbol example. Its code has 4 bits, so four merges sit above it: the nodes 14, 30, 55 and the root 100. Each of those merge weights includes the 5 occurrences of a. So the merge weights count a four times, which is 5 times 4 = 20 bits. Every symbol works the same way, so the sum of all merge weights is the total number of bits.

10. A student says: "Merge the two largest, because they are the most important." Give a small example that shows why this makes the total bigger.

Show the answer

Take frequencies 1, 1, 10, 10. Merging the two largest first (10 and 10) gives 20, then 1 and 1 give 2, then 2 and 20 give 22. The cost is 20 + 2 + 22 = 44. Merging the two smallest first gives 2, then 2 and 10 give 12, then 12 and 10 give 22. The cost is 2 + 12 + 22 = 36, which is smaller.

What you now know

• Common symbols should get short codes. A fixed-length code wastes bits when frequencies are unequal.
• Codes must be prefix-free so the decoder knows where each letter ends.
• Huffman coding merges the two smallest weights at each step, using a min-heap from heapq.
• The total encoded size equals the sum of the merge weights, which is the basis of the cost-only program.
• Test the one-symbol case, and decode a round trip to check your work.

Next lesson: how to prove a greedy rule with an exchange argument, and how to spot the problems where greedy fails.