Build the Code

Finish the Merge Stack

Repeating the merge rule builds the full code tree.

highlighted = computed this step

Repeat the same rule

After CD exists, the queue is A, B, and CD. The same smallest-first rule continues.

repeat smallest-first\text{repeat smallest-first}
Finish the merge stackHuffman rows recomputed from pinned counts and message.Finish the merge stack - 12 fixed bits, 11 Huffman bitsrowvaluecheckcount A5pinned countcount B2pinned countcount C1pinned countcount D1pinned countmerge 1C(1)+D(1)=CD(2)lowest count, then lexicalmerge 2B(2)+CD(2)=BCD(4)lowest count, then lexicalmerge 3BCD(4)+A(5)=root(9)lowest count, then lexicalcode A1left 0, right 1code B00left 0, right 1code C010left 0, right 1code D011left 0, right 1messageABACADpinned messagefixed bits122 bits per symbolhuffman bits11sum code lengthsencoded10010101011message rewritten with codes

B merges with CD

B has count 2, and CD has count 2. The lexical tie puts B first, making BCD with count 4.

B+CD=BCD,∣BCD∣=4B+CD=BCD,\quad |BCD|=4
Finish the merge stackHuffman rows recomputed from pinned counts and message.Finish the merge stack - 12 fixed bits, 11 Huffman bitsrowvaluecheckcount A5pinned countcount B2pinned countcount C1pinned countcount D1pinned countmerge 1C(1)+D(1)=CD(2)lowest count, then lexicalmerge 2B(2)+CD(2)=BCD(4)lowest count, then lexicalmerge 3BCD(4)+A(5)=root(9)lowest count, then lexicalcode A1left 0, right 1code B00left 0, right 1code C010left 0, right 1code D011left 0, right 1messageABACADpinned messagefixed bits122 bits per symbolhuffman bits11sum code lengthsencoded10010101011message rewritten with codes

The last merge makes root

BCD has count 4. A has count 5. Together they make the root with total 9.

4+5=94+5=9
Finish the merge stackHuffman rows recomputed from pinned counts and message.Finish the merge stack - 12 fixed bits, 11 Huffman bitsrowvaluecheckcount A5pinned countcount B2pinned countcount C1pinned countcount D1pinned countmerge 1C(1)+D(1)=CD(2)lowest count, then lexicalmerge 2B(2)+CD(2)=BCD(4)lowest count, then lexicalmerge 3BCD(4)+A(5)=root(9)lowest count, then lexicalcode A1left 0, right 1code B00left 0, right 1code C010left 0, right 1code D011left 0, right 1messageABACADpinned messagefixed bits122 bits per symbolhuffman bits11sum code lengthsencoded10010101011message rewritten with codes

Summary

The merge order is C with D, then B with CD, then BCD with A.

merge order is fixed\text{merge order is fixed}
Finish the merge stackHuffman rows recomputed from pinned counts and message.Finish the merge stack - 12 fixed bits, 11 Huffman bitsrowvaluecheckcount A5pinned countcount B2pinned countcount C1pinned countcount D1pinned countmerge 1C(1)+D(1)=CD(2)lowest count, then lexicalmerge 2B(2)+CD(2)=BCD(4)lowest count, then lexicalmerge 3BCD(4)+A(5)=root(9)lowest count, then lexicalcode A1left 0, right 1code B00left 0, right 1code C010left 0, right 1code D011left 0, right 1messageABACADpinned messagefixed bits122 bits per symbolhuffman bits11sum code lengthsencoded10010101011message rewritten with codes