Huffman coding

Why it matters

Huffman coding is the idea behind many everyday file formats. Compressed archives, image formats and some video formats all use a version of it to store common symbols in fewer bits. For you, the algorithm is valuable for another reason. It is the classic greedy solution that needs a priority queue, and the same pattern of "repeatedly take the two smallest and combine them" shows up in many interview problems: merging ropes, joining files, and minimising costs. Learn it once in full, and you will recognise the pattern later.

Words you will need

• Bit: the smallest unit of storage, with the value 0 or 1.
• Code: a way of writing a symbol, such as a letter, as a string of bits. The letter a might be written as 0 and the letter b as 10.
• Fixed-length code: every symbol gets the same number of bits. ASCII text is a fixed-length code with 8 bits per character.
• Variable-length code: different symbols get different numbers of bits. Frequent symbols get short codes and rare symbols get long ones.
• Frequency: how often a symbol appears in the text.
• Prefix code: a code in which no code is the beginning of another code. The code 10 is a prefix of 101, so the two cannot both be codes.
• Tree: a set of nodes joined by lines, with one top node called the root. A node with no children is a leaf.
• Priority queue: a collection that always gives you the item with the highest (or lowest) priority first.
• Min-heap: a priority queue that gives the smallest item first. In C++ you ask for one by passing greater as the comparison, as this lesson shows.
• Binary tree: a tree in which each node has at most two children, called left and right.

The problem: spending fewer bits

Suppose you store a message that uses only six letters: a, b, c, d, e and f. Each letter appears a number of times, and the counts add up to 100 characters. A fixed-length code needs 3 bits per letter, because three bits give eight patterns and six letters fit in them. So a 100-character message needs 300 bits.

Now look at the counts. Letter a appears 45 times. Letter f appears 5 times. If a gets a 1-bit code and f gets a 4-bit code, the frequent letter saves bits on every use. The question is how to assign the codes so the total number of bits is as small as possible, while the message can still be decoded without any separators between letters. A Huffman code answers both questions.

The everyday comparison is shorthand. A writer who copies a long report by hand may use short marks for words that appear often, such as "the" or "and", and write rare words in full. The short marks make the text quicker to write. A Huffman code does the same for letters, and it is the best such scheme when each letter is coded on its own.

Why a prefix code is needed

A code must be decodable. If the codes are 0, 1 and 01, then the bits 01 could mean 0 followed by 1, or the single code 01. The reader cannot tell which. Separators would fix this, but separators cost bits.

A prefix code avoids separators. No code is the beginning of another code. Take the codes a = 0, b = 10, c = 110 and d = 111. Nothing starts with a code of another letter. A decoder reads one bit at a time. As soon as the bits read so far match a code, that letter is finished, and the decoder starts over. It never has to look ahead.

Decode the bit string 0101101110 with that table. Read 0, which matches a, so output a. Read 1, no match yet. Read 10, which matches b, so output b. Read 110, which matches c, so output c. Read 111, which matches d, so output d. Read 0, which matches a, so output a. The text is abcda. You can see that each match was final, and no letter needed a separator.

A tree is the easiest way to see a prefix code. Start at the root. Each left edge means a 0 and each right edge means a 1. Follow the path for a letter's code, and it ends at the leaf for that letter. Letters sit only at leaves, never in the middle of the tree. That placement is exactly why no code can be the beginning of another.

The Huffman idea

Huffman's method builds the tree from the bottom up. Here is the rule.

1. List every letter with its frequency, as a separate small tree.
2. Take the two trees with the smallest frequencies.
3. Join them under a new parent. The parent's frequency is the sum of the two.
4. Put the new parent back in the list.
5. Repeat until one tree is left.

Then read the codes from the finished tree. Each left edge is a 0, and each right edge is a 1. The code for a letter is the path from the root to its leaf.

Why does this give short codes to frequent letters? A letter is merged early only if its frequency is small, so it is joined near the bottom of the tree, far from the root. Far from the root means a long path, which means a long code. A frequent letter is merged late, when the trees are big. It ends up near the root, with a short path and a short code.

This is a greedy rule. At each step it takes the two smallest trees and joins them, without looking at what the rest of the tree will need. Lesson 4 explains why that choice never hurts.

Why a min-heap is the right tool

Each step needs the two smallest frequencies in the list. The list changes all the time, because each merge removes two trees and adds one. You could sort the list after every merge, but that repeats a lot of work. A min-heap is built for this job. It keeps the smallest item at the top, and taking the top item or adding a new item costs O(log n) time.

The visualizer below shows a heap being filled and emptied. Each item sits in a tree shape, and the smallest one is always at the top, so a removal brings up the next smallest.

Watch what happens when the top item is removed. The shape is rearranged so that the smallest remaining item moves to the top again. That single rule is what lets Huffman coding find its two smallest trees quickly.

The C++ priority queue

C++ provides the heap as std::priority_queue, in the <queue> header. By default it is a max-heap: it gives the largest item first. Huffman needs the smallest first, so you must ask for a min-heap explicitly.

The full type looks long, but it has three parts: the item type, the container that stores the items, and the comparison that decides the order.

priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>>

The item type is a pair, which holds two values: a frequency and the index of a tree in a list. The container is a vector of those pairs. The comparison greater says that a pair with a smaller first value should come out first. Because a pair compares its first value before its second, the heap orders by frequency, and it uses the index only to break ties.

Using an index instead of a pointer keeps the code short and avoids memory leaks. The trees are stored in one vector called nodes, and each node refers to its children by their positions in that vector. The first program below uses that design.

Worked example by hand

Take the six letters with their counts: a 45, b 13, c 12, d 16, e 9 and f 5. The counts sum to 100.

The first merge takes the two smallest, f (5) and e (9). They join under a parent of weight 14. The list is now 12, 13, 14, 16 and 45. The second merge takes c (12) and b (13) into a parent of weight 25. The list is 14, 16, 25 and 45. The third merge takes 14 and 16 into a parent of weight 30. The list is 25, 30 and 45. The fourth merge takes 25 and 30 into a parent of weight 55. The list is 45 and 55. The last merge takes 45 and 55 into the root of weight 100.

The sum of the merged weights is 14 plus 25 plus 30 plus 55 plus 100, which is 224. That number is the total bits for the 100-character message, because each merge adds the frequency of everything under it once for every extra bit. The fixed-length total was 300, so the Huffman code saves 76 bits, which is about 25 percent.

Huffman tree for the six letters, with a at depth 1 and f and e at depth 4

Read the codes from the diagram. The root's left edge goes to a, which gets the code 0. The right edge leads to the node of weight 55. Its left child is the node of weight 25, which holds c and b, so c gets 100 and b gets 101. Its right child is the node of weight 30. That node holds the node of weight 14, with f at 1100 and e at 1101, and d at 111.

The letters with the highest counts, a at 45 and then b, c and d at 12 to 16, get the shortest codes. The rarest letters, e and f, get the longest. The code lengths are 1 for a, 3 for b, c and d, and 4 for e and f.

Program 1: building the codes

The program below reads the letters and their frequencies from the Input box, builds the tree with a min-heap, and prints the code for each letter. It also prints the total number of bits. Type the input below, then press Run.

6
a 45
b 13
c 12
d 16
e 9
f 5

The first number is the count of letters. Each following line has a letter and its frequency.

The output you should see:

a: 0
b: 101
c: 100
d: 111
e: 1101
f: 1100
total bits 224

The codes match the diagram. The total is 224, which equals the sum of the merges from the worked example, as it must. The program computes the total a second way, by adding each letter's frequency times its code length. Getting the same number both ways is a good check that the tree and the codes agree.

Walk through the important lines. nodes.push_back({c, f, -1, -1}) adds a leaf. A leaf has no children, so both child indexes are -1. The while loop takes the two smallest entries from the heap with top and pop. Each top gives a copy of the pair, so pop can remove the entry safely afterwards. auto [f1, a] is a structured binding. It names the two parts of the pair in one line.

The line pq.push({f1 + f2, (int)nodes.size() - 1}) stores the new node and pushes its frequency and index into the heap. The number of nodes grows by one each time, and the last node in the vector is the new parent.

The function assignCodes walks the tree. It adds a 0 to the prefix when it goes left and a 1 when it goes right. At a leaf it stores the prefix. The special case prefix.empty() ? "0" : prefix handles a tree with one letter, where the walk starts and ends at the same leaf. Without it, that letter's code would be the empty string, which cannot be written as bits.

Program 2: decoding a prefix code

Decoding is the reverse of encoding. The program below reads a code table, then a string of bits, and writes out the letters. It collects bits one at a time and checks after each bit whether the collected bits form a code. Because the code is a prefix code, the first match is always right.

Type the input below into the Input box and press Run. The first number is the count of codes. Each code line has a letter and its bits. The last line holds the bits to decode.

4
a 0
b 10
c 110
d 111
0101101110

The output you should see:

decoded: abcda

Now type a bad message into the Input box. Replace the last line with 01011 and press Run. The output is:

leftover bits: 11

The decoder read 0 as a, then 10 as b, then the bits 1 and 1. The pair 11 is not a code yet, and the message ended. The leftover tells you the message is damaged or cut short. Real decoders report such a problem in the same way, because a prefix code makes the error easy to spot.

The map decode connects a code string to its letter. The call decode.find(current) looks up the bits collected so far. If the lookup finds something, the iterator found points to a pair, where found->second is the letter. The current.clear() line empties the collected bits so the next letter starts fresh.

Program 3: printing the merges

A trace of the merges shows the tree being built step by step. This program prints the two trees it joins at each step, with their frequencies, and the new total. It uses a min-heap of pairs, where each pair holds a frequency and a name. The name of a merged tree shows its letters inside brackets.

Type the same six-letter input as Program 1, then press Run.

6
a 45
b 13
c 12
d 16
e 9
f 5

The output you should see:

merge 1: f(5) + e(9) = 14
merge 2: c(12) + b(13) = 25
merge 3: (fe)(14) + d(16) = 30
merge 4: (cb)(25) + ((fe)d)(30) = 55
merge 5: a(45) + ((cb)((fe)d))(55) = 100
sum of all merges 224

Each line is one merge from the worked example. The names show the shape of the tree: (fe) is the node that joins f and e, and ((fe)d) is the node that joins (fe) with d. You can read the final name as the whole tree.

The program's total, 224, is the sum of the merge sums. This is the same number as Program 1's bit count. Two different calculations agreeing is good evidence that both are right.

The line string(1, c) builds a one-character string from the letter c. The first argument is how many copies, and the second is the character. The merged names are built by joining the two names with brackets around them, so each name stays readable.

Program 4: the mistake that uses the wrong heap

The most common Huffman bug is using the default priority queue. The program below makes that mistake on purpose, so you can see the effect. It uses priority_queue<long long> with no comparison, which is a max-heap. It merges the two largest frequencies each time instead of the two smallest.

Use the same six-letter input as before.

The output you should see:

sum of all merges with the wrong heap 416

The correct total is 224, and this program prints 416. Nothing crashes and no warning appears. The tree is still a valid tree, but it is a bad one, because the big letters are merged early and get long codes. This is why the bug is dangerous: the program looks finished, and the answer is only wrong when you check it against the correct value.

The fix is to ask for a min-heap, which Program 1 does with greater. The rest of the algorithm stays the same.

The one-letter case

A Huffman tree for one letter has only one node, which is a leaf. The loop that merges never runs, because it needs two trees. The code for that letter comes from the empty prefix, which is the string of zero bits. A code of zero bits cannot be written or read. The fix in Program 1 gives the letter the code 0, and the total becomes its frequency times 1. This is the only special case in the whole algorithm, and it is the one a beginner most often misses.

Why the total equals the sum of the merges

Program 3 prints the sum of the merges, and Program 1 prints the bit count. They agree, and the reason is worth knowing, because it is the key to the whole method.

Each merge creates a parent, and every letter under that parent gets one more bit of code. A letter's code length is the number of parents above it, which is the number of merges that include it. So each merge adds its sum to the total once for every letter under it, and each letter is counted once for each bit of its code. Adding the merge sums therefore gives the total of frequency times code length, which is the bit count.

Here is a small check you can do on paper. Use four letters: a with frequency 3, b with 1, c with 4 and d with 2. The merges are b and d into 3, then a and that 3 into 6, then c and 6 into the root of 10. The merge sums are 3, 6 and 10, which total 19. Now read the codes from the tree. The root's left child is c, so c gets 0. The right child is the node of 6, whose left child is a, so a gets 10. The node of 6 has a right child, the node of 3, which splits into b at 110 and d at 111. The bit count is 3 times 2 for a, which is 6, plus 1 times 3 for b, which is 3, plus 4 times 1 for c, which is 4, plus 2 times 3 for d, which is 6. That sums to 19, the same as the merges.

With a fixed-length code, four letters need two bits each, so the message would take 2 times 10, which is 20 bits. The Huffman code takes 19. The saving is small here because the letters are close in frequency. The saving grows when the frequencies are very uneven, as in the six-letter example earlier.

Why the two smallest trees are safe

Here is the intuition behind the greedy choice. The exact proof comes in lesson 4, but you can see the idea now.

Imagine a best tree already built for the letters. Its deepest leaves have the longest codes. If a rare letter sits high in the tree while a common letter sits deeper, swap them. The common letter gets the shorter code, and the rare letter gets the longer one. The total number of bits goes down or stays the same, so the swap never hurts.

Repeat this until the two rarest letters sit at the bottom of the tree as siblings, which means they share a parent. That is exactly what the first merge builds. Once they are joined into one item with their combined frequency, the problem looks like a smaller problem with one fewer letter, and the same argument applies again. This is why repeating the merge of the two smallest items gives a best tree, and it is why the greedy rule is safe.

Complexity

With n letters, the algorithm does n minus 1 merges. Each merge removes two items from the heap and adds one, and each heap operation costs O(log n). The total is O(n log n). Building the codes by walking the tree costs O(n), because each node is visited once.

Space is O(n) for the nodes and the codes. Each code can be as long as n minus 1 bits in the worst case, which happens when the frequencies grow like Fibonacci numbers, so the total size of all the codes can be large. For real text the codes stay short.

What happens inside the computer

The heap is a tree stored in an array. The top item sits at position 0. The children of position i sit at positions 2i+1 and 2i+2. The heap keeps itself in order by swapping items up after a push and down after a pop, so each operation takes about log n swaps. You do not need to write that code, but knowing the layout helps you read the visualizer.

The nodes vector grows as the merges add parents. Each push_back may copy the whole vector when it runs out of room, and C++ grows vectors by a fixed factor, so the copies are rare and the average cost per merge stays small. Keeping indexes instead of pointers means that a copy never leaves a dangling reference, which is one reason Program 1 uses indexes.

The second visualizer repeats the heap picture with a different set of values. It is the same structure, and the smallest value always sits at the top.

Common mistakes

The max-heap bug. This is the one in Program 4. The symptom is a total that is too large, with no error. The fix is greater in the priority queue type.

A compile error from a struct without a comparison. Suppose you put a Node struct into priority_queue<Node, vector<Node>, greater<Node>> without defining operator> for it. The compiler stops with this message:

error: no match for ‘operator>’ (operand types are ‘const Node’ and ‘const Node’)

The message says greater needs a > for Node, and there is none. You can fix it by defining the comparison, or by putting a pair of a number and an index in the heap, as Program 1 does.

Giving letters to internal nodes. Only leaves hold letters. An internal node is a merge, and its letter field is a placeholder. If you print a letter for an internal node, you print something that is not in the message. Check that every letter you print sits in the first n positions of nodes.

Forgetting the one-letter case. The code for a single letter must be a single bit. Test with a one-letter input to make sure the output is z: 0. Program 1 prints that for the input 1 and z 7, with total 7.

Decoding without checking the prefix rule. If you build a table where a code is the start of another code, the decoder may match too early and print a wrong letter. A Huffman table never has this problem, but a hand-written table might, so check it first.

Freeing memory in the tree with pointers. Many tutorials build the tree with new and never call delete. Program 1 avoids this by using indexes. If you use pointers in a real program, free the nodes when you are done.

Debugging walkthrough

Suppose your program prints a code that is longer than you expected for a frequent letter. Follow these steps.

First, check the merge order. Run Program 3 on your input. The two smallest frequencies should be merged first. If a large one appears in the first merge, the heap is the wrong kind, or the comparison is reversed.

Second, check the total. Compute the sum of the merge sums by hand, and compare it with the program's total. If they differ, the tree was built with the wrong pairs.

Third, check the codes against the tree. Draw the tree on paper, using the merge order, and read the codes from it. Compare with the program's output, letter by letter.

If the codes are right but the decoding is wrong, test the decoder with a short message, such as one letter at a time. A decoder that goes wrong on the second letter usually has a table with a prefix error or a missing current.clear().

Variations and edge cases

Equal frequencies. When every letter has the same frequency, the merges have many ties. Different tie-breaking gives a different tree, with different codes, but the same total. Programs 1 and 3 may print different codes from another version of the algorithm. The total is what matters for compression.

One letter. Covered above. The code is 0 and the total is the frequency times 1.

Two letters. The tree has one merge. Each letter gets a code of one bit. The total is the sum of the two frequencies.

Codes are not unique. Swapping the left and right children of any node gives a different valid code table with the same lengths. Lengths and totals are unique, bit strings are not.

Real file formats. Many compression formats combine Huffman coding with another step that finds repeated patterns in the data. The idea in this lesson is the Huffman part. You do not need the other part to understand the algorithm, but an interviewer may ask how real tools use it.

Interview questions you will hear

The usual question is to build a Huffman code for a list of frequencies and report the total bits. The answer uses a min-heap, n minus 1 merges, and O(n log n) time. The second usual question is why the greedy choice is safe. Lesson 4 gives the exchange argument, which says the two rarest letters can always be siblings at the bottom of an optimal tree.

A related problem is the minimum number of rooms for meetings. It can be solved with a min-heap of end times. Sort the meetings by start time. For each meeting, if the earliest end time in the heap is at or before its start, reuse that room by removing the end time. Then add the new end time. The heap size at the end is the number of rooms. That problem appears in the coding problems for this module.

Practice

1. Easy. Merge by hand. Frequencies 1, 1, 2 and 3 are merged with the Huffman rule. What are the merge sums, and what is the total?

2. Easy. Why not both? Explain why 0 and 01 cannot both be codes in a prefix code.

3. Easy. Decode. With codes a = 0, b = 10 and c = 11, decode the bits 1011.

4. Medium. Equal frequencies. Six letters each have frequency 10. Give the code lengths the Huffman rule produces, and the total bits.

5. Medium. Compute a total. Frequencies are 5, 5, 10, 20 and 60, which sum to 100. Find the merge sums and the total.

6. Medium. Longest code. Change Program 1 so it prints the length of the longest code at the end.

7. Medium. A struct comparison. Write operator> for a struct Node with a field freq, so that priority_queue<Node, vector<Node>, greater<Node>> gives the smallest frequency first.

bool operator>(const Node& a, const Node& b) {
    return a.freq > b.freq;
}

8. Medium. Rooms with a heap. Describe, with a short code sketch, how to find the fewest rooms for meetings using a min-heap of end times.

9. Medium. One letter. A message has only the letter q with frequency 9. What code does Program 1 give it, and what is the total bits?

10. Hard. The safe first step. Explain in three sentences why the two least frequent letters can always be made siblings at the bottom of some best tree.

11. Hard. Savings. The fixed-length code for the six-letter message uses 300 bits. The Huffman code uses 224 bits. What fraction of the bits does the Huffman code save?

12. Hard. Decoder by tree. Describe a decoder that uses the tree instead of a table of codes. Explain why it needs no lookup table and why it stops at the right letter.

What you now know

• A variable-length code gives short codes to frequent letters, and a prefix code stays decodable without separators.
• The Huffman rule repeatedly merges the two smallest trees, and the codes are read from the finished tree.
• A min-heap gives the two smallest items in O(log n) each, so the whole build is O(n log n).
• The C++ priority queue is a max-heap by default. You must pass greater to get a min-heap.
• The one-letter case needs a special code of one bit.
• Decoding a prefix code reads bits until they match a code, and the first match is always right.
• The total bits can be checked two ways, by summing the merges and by summing frequency times code length.