Huffman Coding

Question

What is the time complexity of Huffman coding using heap tree data structure ?

a) O(n)

b) O(n log n)

c) O(log n)

d) O(n²)

Answer 1

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.

Comments

means huffman coding always done in min heap?

---

it is efficient, otherwise complexity may increase.

---

Huffmann coding can also be done through sorting but complexicity can be increases to O(n²).

When you have a problem where you have to extract and then insert data again (Like in case of huffmann) it is recommended to use haep.

Answer 2

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).

Comments

where is huffman coding part?