I'm trying to make a huffman tree based off of some words. I have the frequencies of each character stored using a hashtable, but i need to then make a minheap structure in order to then be able to make the huffman tree. What I don't get is how I am supposed to actually use the minheap because I don't understand how I am going to be able to tell (looking through the minheap) what chars freq I am actually looking at.
Just as an additional comment, if the symbols are already sorted in increasing frequency order, Huffman tree construction can be done in linear time.
q1 <- a queue initialised with the symbols in increasing frequency order q2 <- an empty queue while there is more than one element in q1 and q2 do: Find the two elements with the lowest frequencies. (You only need to look at the first two elements in q1 and q2.) Pop them, merge the elements. Push the merged element onto q2.