You are given a string and the frequency of its characters in an integer array. Write an encoding algorithm to compress the data in it losslessly.
We can use Huffman coding using min heap implemented as priority queue. The algorithm works as :
Since each insertion in the priority queue takes O(logn) time and number of nodes for n unique characters in the string is 2n-1 Therefore Time complexity = O(nlogn). Example - /* Main function to build Huffman tree and print code */ |