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.