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.
4 Answers
$\begingroup$
$\endgroup$
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.
answered Dec 16, 2021 at 23:37
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ But you will need the frequency of the combined item. Letter x = 0.17%, letter r = 0.25%, (letter x or r) = 0.42%. $\endgroup$ Commented Jan 11, 2023 at 9:05
$\begingroup$
$\endgroup$
It can be divided basically into three steps:
Step 1: For each character of the node, create a leaf node. The leaf node of a character contains the frequency of that character.
Step 2: Set all the nodes in sorted order according to their frequency.
Step 3: There may exist a condition in which two nodes may have the same frequency. In such a case, do the following:
Create a new internal node. The frequency of the node will be the sum of the frequency of those two nodes that have the same frequency. Mark the first node as the left child and another node as the right child of the newly created internal node.
$\begingroup$
$\endgroup$
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.
