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?

  • $\begingroup$ 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. $\endgroup$ Apr 1, 2020 at 22:10
  • $\begingroup$ 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. $\endgroup$
    – Pseudonym
    Apr 1, 2020 at 22:39
  • $\begingroup$ @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. $\endgroup$
    – NewDev90
    Apr 2, 2020 at 0:34


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.