Huffman Coding

Interactive Visualization · BCS 309 · Spring 2026
Input
a:5
b:2
r:2
c:1
d:1
Playback
1x
Step 33 / 33 Done
Statistics
8
Extractions
4
Merges
22
Comparisons
23
Bits (encoded)
Pseudocode
1 HUFFMAN(text):
Entry point: receive input text
2 freq = COUNT_FREQ(text)
Count how many times each character appears — O(n)
3 Q = BUILD_MIN_HEAP(freq)
Create a min-heap with one leaf node per character — O(n)
4 while |Q| > 1:
Repeat until only the root remains — runs n-1 times
5 x = EXTRACT_MIN(Q)
Remove node with smallest frequency — O(log n)
6 y = EXTRACT_MIN(Q)
Remove second smallest frequency — O(log n)
7 z = NEW_NODE()
Create a new internal node
8 z.freq = x.freq + y.freq
Sum the frequencies of the two children
9 z.left = x; z.right = y
Attach x as left child, y as right child
10 INSERT(Q, z)
Insert merged node back into heap — O(log n)
11 root = EXTRACT_MIN(Q)
Final node is the root of the Huffman tree
12 ASSIGN_CODES(root, "")
Traverse tree, assigning 0 for left, 1 for right edges
13 return codes
Return the mapping of characters to binary codes
Step Explanation
Done! Codes assigned. Encoded "abracadabra" uses 23 bits vs 88 bits (fixed).
History
#ActionNodesResult
4 extract c 0 merges
5 extract + d 0 merges
6 merge c + d 1 merges
7 merge 1 merges
8 merge 1 merges
9 insert 1 merges
10 check 1 merges
11 extract _merge1 1 merges
12 extract + b 1 merges
13 merge _merge1 + b 2 merges
14 merge 2 merges
15 merge 2 merges
16 insert 2 merges
17 check 2 merges
18 extract r 2 merges
19 extract + _merge2 2 merges
20 merge r + _merge2 3 merges
21 merge 3 merges
22 merge 3 merges
23 insert 3 merges
24 check 3 merges
25 extract a 3 merges
26 extract + _merge3 3 merges
27 merge a + _merge3 4 merges
28 merge 4 merges
29 merge 4 merges
30 insert 4 merges
31 done 4 merges
32 codes 4 merges
33 done 4 merges
🌳 Huffman Tree
📊 Min-Heap
🌳+📊 Combined
🔢 Encode/Decode
📈 Complexity
⚡ Greedy
📚 Learn
01010101 11 a 5 0 6 r 2 10 4 2 c 1 1100 d 1 1101 b 2 111
Internal Node
Leaf (Character)
Currently Merging
Just Extracted
Final Tree
11 ∅ Index (min-heap order):0
In Heap
Being Extracted
Merged / Inserted
🌳 Huffman Tree
01010101 11 a 5 0 6 r 2 10 4 2 c 1 1100 d 1 1101 b 2 111
Internal Node
Leaf (Character)
Currently Merging
Just Extracted
Final Tree
📊 Min-Heap
11 ∅ Index (min-heap order):0
In Heap
Being Extracted
Merged / Inserted
Huffman Codes
CharFreqCodeBitsFixed (8-bit)
c 1 1100 4 8 → 4 (50% less)
d 1 1101 4 8 → 4 (50% less)
b 2 111 3 16 → 6 (63% less)
r 2 10 2 16 → 4 (75% less)
a 5 0 1 40 → 5 (88% less)
Encode Text
—
Decode Binary
—
3002001000135791113151719n (distinct characters)OperationsHuffman — O(n log n)Shannon-Fano — O(n²)Arithmetic Coding — O(n)
AlgorithmBest CaseAverage CaseWorst CaseSpace
Huffman Coding O(n log n) O(n log n) O(n log n) O(n)
Shannon-Fano O(n log n) O(n log n) O(n²) O(n)
Arithmetic Coding O(n) O(n) O(n) O(n)
⚠ Worst Case for Huffman Huffman Coding's complexity is always O(n log n) — there is no asymptotically worse case. However, the compression ratio is worst when all n characters have equal frequency: every code gets the same length, giving zero benefit over fixed-length encoding. The tree becomes perfectly balanced, and you still pay for all n−1 merge operations.
⚡ Greedy Paradigm Huffman Coding is a greedy algorithm. At each step, it makes the locally optimal choice: always merge the two nodes with the smallest frequencies. This greedy choice property guarantees a globally optimal prefix-free code.
Greedy Choices Made
1
Greedy Choice #1
Create internal node with frequency 1 + 1 = 2.
2
Greedy Choice #2
Set merged node frequency = 2.
3
Greedy Choice #3
Attach "c" as left child, "d" as right child.
4
Greedy Choice #4
Create internal node with frequency 2 + 2 = 4.
5
Greedy Choice #5
Set merged node frequency = 4.
6
Greedy Choice #6
Attach "∅" as left child, "b" as right child.
7
Greedy Choice #7
Create internal node with frequency 2 + 4 = 6.
8
Greedy Choice #8
Set merged node frequency = 6.
9
Greedy Choice #9
Attach "r" as left child, "∅" as right child.
10
Greedy Choice #10
Create internal node with frequency 5 + 6 = 11.
11
Greedy Choice #11
Set merged node frequency = 11.
12
Greedy Choice #12
Attach "a" as left child, "∅" as right child.
What if we used a different paradigm? If we used a random merge order (instead of greedy minimum), the resulting codes would be suboptimal — the total bits needed would be larger. For "abracadabra": greedy gives 23 bits, a random merge gives more.
Proof of Optimality (Exchange Argument) Suppose the two lowest-frequency symbols are x and y. In any optimal tree, x and y must be siblings at the deepest level — otherwise swapping them with deeper siblings would reduce total cost. Therefore, the greedy choice of always merging the minimum two is safe.
📖 What is Huffman Coding? ▼

Huffman Coding is a lossless data compression algorithm invented by David A. Huffman in 1952. It assigns variable-length binary codes to characters based on their frequency of occurrence.

Characters that appear more often get shorter codes; rare characters get longer codes. This is the opposite of fixed-length encoding (e.g., ASCII uses 8 bits per character regardless of frequency).

When to use it:

  • Compressing text files (used in ZIP, GZIP)
  • Image compression (JPEG uses Huffman as a final step)
  • Any scenario where symbol frequencies vary greatly

Key property:

Huffman codes are prefix-free: no code is a prefix of another, so they can be decoded unambiguously without separators.

🔍 How does the algorithm work? ▼

Step-by-step:

  • 1. Count frequencies of each character in the input.
  • 2. Build a min-heap (priority queue) of leaf nodes, one per character.
  • 3. Repeat until one node remains:
    • Extract the two nodes with minimum frequency (extract-min twice).
    • Create a new internal node with their sum as frequency.
    • Insert the new node back into the heap.
  • 4. The remaining node is the root of the Huffman tree.
  • 5. Assign codes: traverse from root; left edge = 0, right edge = 1.

Complexity:

With a binary min-heap: O(n log n) where n = number of distinct characters. Each of the n-1 merge steps requires two extract-min (O(log n)) and one insert (O(log n)).

📝 Worked Example: "abracadabra" ▼

Frequencies:

a=5, b=2, r=2, c=1, d=1

Heap initially:

[c:1, d:1, b:2, r:2, a:5]

Step 1 — Merge c:1 and d:1:

New node cd:2. Heap: [b:2, r:2, cd:2, a:5]

Step 2 — Merge b:2 and r:2:

New node br:4. Heap: [cd:2, a:5, br:4]

Step 3 — Merge cd:2 and br:4:

New node cdbr:6. Heap: [a:5, cdbr:6]

Step 4 — Merge a:5 and cdbr:6:

Root: 11. Tree complete!

Resulting codes:

a=0, b=110, r=111, c=100, d=101

Total bits = 5×1 + 2×3 + 2×3 + 1×3 + 1×3 = 23 bits vs 11×8 = 88 bits fixed

⚠ Common Mistakes ▼
Mistake 1: Forgetting prefix-free property Huffman codes are prefix-free by construction (path from root to leaf), but manually assigned codes might not be. Always build the tree properly.
Mistake 2: Using sorting instead of min-heap If you re-sort after each merge, complexity becomes O(n²). The min-heap is essential for O(n log n).
Mistake 3: Huffman ≠ optimal for all cases For uniform distributions (all equal frequencies), Huffman gives no compression advantage. Arithmetic coding can achieve better compression in those cases.
🔗 CLO Coverage Summary ▼
CLO-1: Asymptotic Analysis See the Complexity tab. O(n log n) with min-heap. Growth chart shows actual vs theoretical operations. Worst case preset available.
CLO-2: Sorting & Searching The Min-Heap tab shows heap operations. "Search for minimum" is the extract-min at each step, highlighted in orange. Without the heap (using linear scan), complexity degrades to O(n²).
CLO-3: Greedy Paradigm See the Greedy tab. Each greedy choice (merge two smallest) is animated. The exchange argument proof is shown. Comparison with random merge demonstrates suboptimality.