4,439 views

2 Answers

Best answer
4 votes
4 votes

If there are n characters in Huffman Coding then we can build a min heap in nlogn.

then 2 times extract-min will take logn, after that insertion of result will also take logn. and this will be repeated for i=1 to n-1;

So, total complexity will be nlogn.

selected by
2 votes
2 votes
Suppose there are n characters on which we apply Huffman encoding. We arrange them into Min Heap data structure on the basis of their frequency of occurance because we require character with minimum occurance in each iteration.

Step 1: Create Minheap using BuildHeap algorithm. It'll take O(n) time for n keys.
Step 2: Delete two minimum(2 logn) and one insertion (log n). This takes n-1 steps. So (n-1)*(2 logn + logn) = O(n logn)
Total time complexity = O(n) + O(n log n) = O(n log n).
edited by

Related questions

1 votes
1 votes
2 answers
1
Akash Kumar Roy asked Apr 26, 2018
3,943 views
what is Space complexity of Huffman coding?
1 votes
1 votes
3 answers
3
Parshu gate asked Nov 16, 2017
2,594 views
The following message is: GATE2018GAATTTEEEE22000011188What is the average length of bits required for encoding each letter using Huffman coding___?
2 votes
2 votes
1 answer
4
atul_21 asked Nov 13, 2017
683 views