huffman coding

Question

how to find the comparision complexities in huffman coding algorithm?

Comments

what it mean by comparison complexity?

---

like in merge sort it is O(m+n-1)

Answer 1

It is not Huffman Coding.
It is Optimal merge pattern problem.
The below image might help you
 

Answer 2

I guess you are talking about complexity of huffman coding.

1.We have n keys,and we need to merge tree n-1 time to generate final tree.

2.we use min heap to store frequency of every node.

3.In ever iteration we find out top two min frequencies ------->logn time

4.Then we merge those two frequencies and insert in the tree again---->logn

we repeat this process n- 1 time,then total complexity of huffman coding is =(n-1)*(3logn)=O(nlogn)

Comments

i wan t to know about comparisions

ex:

10,3,3,1    these are the length of the file which we need to merge

sort--- 1,3,3,10

1+3-1=3

3+4-1=6

7+10-1=16

total comparision =  3+6+16=25 ?

is it correct approach i m confuse plz clear my doubt

---

i guess you are confusing huffman coding with mergesort or merging procedue.

In huffman coding we only add frequencies of characers in a file.

---

https://gateoverflow.in/466/gate1999-2-20