Issues with a Reference Code for Running Canonical Huffman Code on Java

Question

I am running the Java program shown here to generate canonical Huffman codes, https://www.geeksforgeeks.org/canonical-huffman-coding/

Although the code gives the correct canonical Huffman codes with the shown input, for other cases I don't find the codes to be prefix code and correct. For example ,

    **Input**

    char[] chararr = {  '0',  '1',  '2', '3', '4',  '5', '6', '7', '8', '9'};
    int[] freq = {119,173 ,186 ,134 ,134 ,8 ,220 ,216 ,145 ,10 };

   **Output**

   1:0
   2:1
   3:10
   4:11
   6:100
   7:101
   8:110
   0:1110
   5:11110
   9:11111

The logic of assigning canonical codes in the given code seems to be correct; however, I am not getting the correct results, which might be due to the earlier stage of finding code lengths for the given character set and freq. Any help with debugging this Java code will be appreciated.

Answer 1

It is generating the codes correctly, but then printing them incorrectly. It is leaving off the leading zero bits of the codes that have them. They should have prepended the necessary zero bits after converting the number to a string of digits.

If you replace the line that prints the code with this:

// Display the canonical codes
String code = Integer.toBinaryString(c_code);
while (code.length() < curr_len)
    code = "0" + code;
System.out.println(it.next() + ":" + code);

Then you get the correct output:

1:000
2:001
3:010
4:011
6:100
7:101
8:110
0:1110
5:11110
9:11111