Huffman Coding Visualizer

Visualize frequency counting, greedy node merging, Huffman tree construction, and variable-length prefix code generation.

Ready. Use the controls to begin exploring Huffman Coding.

Huffman Coding Visualizer

Speed:

Merge lowest two: C (1) + D (1) = 2

Priority Queue (by frequency)

Step

1 / 5

Java Implementation

class Node {
    char ch;
    int freq;
    Node left, right;
}

public Node buildHuffmanTree(Map<Character, Integer> freq) {
    PriorityQueue<Node> pq = new PriorityQueue<>(
        (a, b) -> a.freq - b.freq
    );
    for (var entry : freq.entrySet()) {
        Node leaf = new Node();
        leaf.ch = entry.getKey();
        leaf.freq = entry.getValue();
        pq.add(leaf);
    }

    while (pq.size() > 1) {
        Node left = pq.poll();
        Node right = pq.poll();
        Node merged = new Node();
        merged.freq = left.freq + right.freq;
        merged.left = left;
        merged.right = right;
        pq.add(merged);
    }

    return pq.poll(); // root of the Huffman tree
}
Time Complexity: O(n log n)

What is Huffman Coding?

Huffman Coding is a greedy algorithm used for lossless data compression. It assigns shorter binary codes to more frequent characters and longer codes to rarer ones, guaranteeing no code is a prefix of another so the encoded stream can be decoded unambiguously.

The algorithm repeatedly makes the locally optimal choice - always merging the two least-frequent nodes in the priority queue - and this greedy strategy provably produces a globally optimal prefix code, unlike Dijkstra's Algorithm which is greedy over graph distances instead of frequencies.

Time & Space Complexity

Build Frequency TableO(n)
Build Huffman TreeO(k log k)
Encode InputO(n)
SpaceO(k)

* n = length of the input text, k = number of distinct characters.

Real-World Use Cases

✓
File CompressionUsed as a component in ZIP, GZIP, and PNG compression formats.
✓
JPEG ImagesApplied after quantization to compress image data further.
✓
MP3 & Video CodecsEntropy coding stage in many multimedia compression pipelines.

Huffman Coding Complete Info Card

Greedy AlgorithmLossless Compression

Huffman Coding greedily merges the two least-frequent nodes in a priority queue over and over, building a binary tree whose leaf depths become optimal prefix code lengths.

Algorithm Characteristics

Build Tree Time

k = number of distinct characters, using a min-heap

O(k log k)

Encode Time

One code lookup per input character

O(n)

Space Complexity

Tree and code table sized by distinct characters

O(k)

Prefix-Free

No code is a prefix of another, so decoding is unambiguous

Yes

Optimality

Produces the minimum possible weighted code length

Yes

Greedy Choice

Always combines the two least-frequent nodes first

Merge 2 smallest

Tree Construction Steps

Count the frequency of every character

Insert one leaf node per character into a min-heap

Remove the two lowest-frequency nodes

Merge them into a new internal node (sum of frequencies)

Insert the merged node back into the heap

Repeat until one node (the root) remains

When to Use

•Skewed character frequency distributions
•As an entropy-coding stage inside a larger compression format
•When decoding speed and simplicity matter

When to Avoid

•Roughly uniform symbol frequencies (little to gain)
•Very small inputs, where the code table overhead dominates
•When adaptive/arithmetic coding could squeeze out more ratio

Did You Know? Huffman coding is provably optimal among all prefix codes for a known frequency distribution - no other prefix code achieves a shorter expected length.

Priority queueBinary treeCompression