huffman tree without using priority queues

Question

for my project i have to create a huffman tree project, but my lecturer has said that i cannot use priority queues to build it? But i dunno how to implement that. Are there any other ways i can create a huffman tree without using priority queues?

This is an example of a huffman tree but it is using priority queues enter image description here enter image description here

Answer 1

There's a trick that is often used to build Huffman trees in practice:

1. Create a list of your symbols with probabilities, and sort it in ascending order

2. Create an initially empty list for combined symbols. This will remain sorted as we work.

3. While there is more than one symbol in the lists:

   1. Remove the two smallest symbols from the beginnings of two lists
   2. Combine them and add them to the end of the combined list. Because the new symbol has a higher combined probability than any combined symbol created before, this list remains sorted.

After the initial sorting, the smallest probability symbol will always be the first one of one of the two lists, so no priority queues or searching is required to find it.

This technique is quite clever, and your lecturer would not expect you to think of it yourself, so it was probably taught or referenced in class.