# Is using Fibonacci Heaps in Huffman Code, better than a regular Min-heap?

When using Huffman Code, to generate prefix-code trees for a sequence of letters, CLRS choose to use a normal Min-heap data structure.

Using Fibonacci-heaps instead, are we not able to achieve a better bound on the running time, knowing that especially the INSERT operation of Fibonacci-heaps are constant time amortized, compared to worst-case $$\theta(\log n)$$ in a regular Min-heap?

I have tried to search online, without finding a solid reference, of the use of Fibonacci-heaps in Huffman code?

Can anyone explain to me if this is a practice, or in the case it is not, why Fibonacci-heaps is not a better pick than a regular Min-heap structure, when we use a sequence of Extract-min and Insert-operations?

• For the Huffman algorithm the sequence of operations is very strict: insert-all (makeheap), and then, until only a single tree remains, twice delete-min followed by insert. Optimizing a single operation won't help. Apr 1, 2020 at 22:10
• If the letters are pre-sorted by frequency, Huffman trees can be computed in $O(n)$ time and $O(n)$ space, where $n$ is the number of letters. Left as an exercise. Apr 1, 2020 at 22:39
• @HendrikJan Hmm that makes sense. Intuitively I can see why optimizing a single operation won't do much, but if we consider a very large set of characters, then we would make sufficiently many Insert operations after each two Extract-min. And in that case won't the constant time amortized Insert operation perform better than that of the regular min-heap? Though I can see the difference is only marginal. Apr 2, 2020 at 0:34