Huffman Encoding — Greedy + Heap

Merge the two smallest, forever

Huffman builds an optimal prefix code: frequent characters get short bit strings, rare ones get long. The greedy rule is beautifully simple. Put every character in a min-heap keyed by frequency, then repeatedly pop the two smallest, merge them under a new parent whose weight is their sum, and push that parent back.

After n-1 merges one tree remains. Read 0 for left, 1 for right down to each leaf to get its code. Because the two rarest symbols merge first, they end up deepest (longest codes), which is exactly what minimizes total encoded length. No two codes are prefixes of each other, so decoding is unambiguous.

// min-heap of nodes by weight
while heap.size() > 1:
  a = heap.pop() # smallest
  b = heap.pop() # 2nd smallest
  p = Node(a.w + b.w, a, b)
  heap.push(p)
return heap.pop() # the root

Time Complexity

O(N log N)

N-1 merges, each two pops and one push on a heap of N nodes.

Space Complexity

O(N)

The heap and the resulting tree both hold O(N) nodes.

Live Visualization

text = frequencies are counted from this text

Two smallest (merging) New parent node Leaf (character) Internal node

Forest heap min-heap by weight

Huffman tree so far (0 = left, 1 = right)

Codes (assigned once the tree is complete)

popped A = – popped B = – merged = – heap size = 0

Step 0 / 0

Two smallest

–

popped this merge

New weight

–

a.w + b.w

Heap size

trees remaining

Encoded bits

–

vs fixed-length

Enter text and hit Play to build the Huffman tree by merging the two rarest nodes.

✓ Done Speed

Step-by-step trace

#	Action	Popped A	Popped B	New node	Heap (weights)

C++ — Huffman tree construction

struct Node {
    int w;              // weight (frequency)
    char ch;            // only meaningful on leaves
    Node *l = nullptr, *r = nullptr;
};
struct Cmp { bool operator()(Node* a, Node* b){ return a->w > b->w; } };

Node* buildHuffman(unordered_map<char,int>& freq) {
    priority_queue<Node*, vector<Node*>, Cmp> pq;   // min-heap by weight
    for (auto& [c, f] : freq) pq.push(new Node{f, c});

    while (pq.size() > 1) {
        Node* a = pq.top(); pq.pop();   // smallest
        Node* b = pq.top(); pq.pop();   // 2nd smallest
        Node* p = new Node{a->w + b->w, '\0', a, b};
        pq.push(p);                     // parent back into heap
    }
    return pq.top();   // root of the Huffman tree
}

// assign codes: go left = '0', right = '1'
void assign(Node* n, string code, unordered_map<char,string>& out) {
    if (!n->l && !n->r) { out[n->ch] = code.empty() ? "0" : code; return; }
    assign(n->l, code + "0", out);
    assign(n->r, code + "1", out);
}

📝 My Notes ●

▾

Saved 0 chars