Say I have many repetitive entries that are to be merged into a Huffman Coding tree. Simply merging them would cost n*logn but I want it to be faster. Say I have 100000 entries of the same frequency 1, then the brute-force Huffman tree building will merge
50000 times at first, which is very slow.
My instructor told me that, we can directly consider it to be (2,50000), (4, 25000) and so on, which is much faster. Yet I have no idea how to implement it. (An explanation with Cpp code would help me a lot 😉
Phere Salad is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
If all of your “entries”, which I take to mean symbols, have the same frequency, then you don’t need to build a Huffman tree at all.
Given n symbols, find the largest power of two, call it k, such that k ≤ n. Then code the first 2k – n symbols using lg k bits, and the remaining 2(n – k) symbols using 1 + lg k bits. You make this a prefix code by appending one bit to the end for the second set of symbols. That gives an optimal prefix code.
So if n = 5, we have k = 4 and lg k = 2. The first three symbols are coded using two bits:
00
01
10
and the remaining two symbols are coded with three bits, adding a bit on the right after incrementing the previous two-bit code:
110
111
For n = 11:
000
001
010
011
100
1010
1011
1100
1101
1110
1111