0
$\begingroup$

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.

$\endgroup$

3 Answers 3

0
$\begingroup$

If you have only 256 symbols, then you can afford brute force: Take the two elements with lowest frequency and combine them, repeat until only one element is left. Takes 256^2 instead of 256 log 256 steps.

$\endgroup$
0
$\begingroup$

If you have a min heap you don't need to know the frequency: the top is the one with the minimum. Just pop two items, join them and add the new item to the min heap. Ideally the frequency is stored in the value of the item stored.

$\endgroup$
0
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.