Huffman coding
Huffman coding is a lossless data compression algorithm. In this algorithm, a variable-length code is assigned to input different characters. The code length is related to how frequently characters are used. Most frequent characters have the smallest codes and longer codes for least frequent characters.
There are two major steps in Huffman Coding-
· Building a Huffman Tree from the input characters.
· Assigning code to the characters by traversing the Huffman Tree.
Time Complexity
The time complexity analysis of Huffman Coding is as follows-
· extractMin( ) is called 2 x (n-1) times if there are n nodes.
· As extractMin( ) calls minHeapify( ), it takes O(logn) time.