A tie in the merge queue — Huffman coding
exam standardwhy your tree may differ from the book's
Answer
b=00 a=01 d=10 c=11
2 merge tie(s) were broken by rule, so other trees of exactly the same cost exist. Moffat (2019) §2.2: symbols are numbered 0…m−1 in ascending code-point order, and the heap is keyed on the tuple (weight, isInternal ? 1 : 0, tieRank) with tieRank = −symbolIndex for leaves and the creation sequence number for internal nodes. So: on a tie between leaves the higher-numbered symbol is preferred; on a tie between a leaf and an internal node the leaf is preferred; on a tie between internal nodes the one formed earlier is preferred. The first node popped becomes the 0 (left) child.
Why this example is worth doing
When two nodes have equal weight the algorithm has a genuine choice, and different choices give different trees with identical average length. This is the single most common reason a student thinks the tool is wrong. The page states its tie-break rule explicitly as a full sort key, shows an example where the alternative tree is equally optimal, and gives the canonical code so the two can be compared on equal terms.
Try your own input in the Huffman coding. Build the tree from text or from frequencies, with the merge order and canonical codes.
How the answer is reached
Tie-break
Moffat (2019) §2.2: symbols are numbered 0…m−1 in ascending code-point order, and the heap is keyed on the tuple (weight, isInternal ? 1 : 0, tieRank) with tieRank = −symbolIndex for leaves and the creation sequence number for internal nodes. So: on a tie between leaves the higher-numbered symbol is preferred; on a tie between a leaf and an internal node the leaf is preferred; on a tie between internal nodes the one formed earlier is preferred. The first node popped becomes the 0 (left) child.
Merge order
| step | left | right | weight |
|---|---|---|---|
| 1 | 1 | 1 | 2 |
| 2 | 2 | 2 | 4 |
| 3 | 2 | 4 | 6 |