Huffman Coding

Greedy O(n log n) O(n)

Builds an optimal prefix code: repeatedly merge the two least frequent trees, then read codes off the root-to-leaf paths.

Text

1/20

Start with 5 single-leaf trees, one per character.

InvariantMerging the two lightest trees puts the rarest symbols deepest, so their long codes cost the least.

picked (two minima)mergedcode emitted

huffman-coding.c

typedef struct Node {
    char ch;
    int freq;
    struct Node *left, *right;
} Node;
 
Node *buildHuffman(Node *forest[], int n) {
    while (n > 1) {
        int a = minIndex(forest, n, -1);
        int b = minIndex(forest, n, a);
        Node *m = newNode(forest[a]->freq
                        + forest[b]->freq);
        m->left  = forest[a];
        m->right = forest[b];
        forest[a] = m;               /* replace one    */
        forest[b] = forest[--n];     /* drop the other */
    }
    return forest[0];
}
 
void printCodes(Node *t, char buf[], int d) {
    if (!t->left && !t->right) {
        buf[d] = '\0';
        printf("%c: %s\n", t->ch, buf);
        return;
    }
    buf[d] = '0'; printCodes(t->left,  buf, d + 1);
    buf[d] = '1'; printCodes(t->right, buf, d + 1);
}

How Huffman Coding works

Merge the two rarest symbols under one node, treat the pair as one symbol, and repeat. Rare symbols end up deep (long codes), frequent ones shallow (short codes); tree paths give prefix-free codes.

When to use it

Entropy coding in compression: DEFLATE/zip, JPEG, MP3 all embed Huffman stages.