Algorithm Guidecomplexity: O(n log n)

Huffman Coding

Compresses data by giving frequent characters short bit codes and rare ones long codes. A greedy strategy that repeatedly merges the two lowest-frequency nodes into a tree produces an optimal prefix code.

01Huffman Coding

Explore How It Works

Start Huffman coding. Frequencies a:5, b:2, c:1, d:1. Repeatedly merge the two smallest into a tree.

Merge the two smallest, c(1) and d(1), into a parent(2).

Next merge b(2) with the node(2) just built into a parent(4).

Finally merge a(5) with the node(4) into the root(9). Tree complete.

Reading left=0, right=1 gives a=0, b=10, c=110, d=111. The frequent a gets the shortest code, shrinking the total length.

Live Python

1import heapq

3def huffman(freq):

4 heap = [[w, sym] for sym, w in freq.items()]

5 heapq.heapify(heap)

6 while len(heap) > 1:

7 lo = heapq.heappop(heap) # two smallest

8 hi = heapq.heappop(heap)

9 merged = [lo[0] + hi[0], lo, hi]

10 heapq.heappush(heap, merged) # merge and push back

11 return heap[0]

1 / 5

02 Understand It Simply

For Everyone

🔑How It Works

Frequent characters get short codes and rare ones get long codes. No code is a prefix of another, so the stream decodes without separators.

💡In Plain Words

Repeatedly merges the two lowest-frequency items into a tree and assigns short bit codes to frequent characters.

The result minimizes total data length.

📍Where It's Used

–File compression (ZIP
–JPEG)
–data-transfer encoding

03 Python Implementation

A clean, readable reference implementation of the core logic of Huffman Coding.

core_implementation.py

import heapq

def huffman(freq):
    heap = [[w, [sym, ""]] for sym, w in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return sorted(heapq.heappop(heap)[1:])

04 Frequently Asked Questions

FAQ

What is Huffman Coding?+

What is the time complexity of Huffman Coding?+

The time complexity of Huffman Coding is O(n log n). Follow the step-by-step visualization to see exactly why.

Where is Huffman Coding used?+

File compression (ZIP, JPEG), data-transfer encoding.

What's a simple analogy for Huffman Coding?+

Frequent characters get short codes and rare ones get long codes. No code is a prefix of another, so the stream decodes without separators.

→ Greedy — see allRelated

🎯Coin Change (Greedy)

O(n)

🎯Activity Selection

O(n log n)