3
$\begingroup$

I'm studying binomial heaps in anticipation for my finals and the CLRS book tells me that insertion in a binomial heap takes $\Theta(\log n)$ time. So given an array of numbers it would take $\Theta(n\log n)$ time to convert it a a binomial heap. To me that seems a bit pessimistic and like a naive implementation. Does anyone know of a method/implementation that can convert an array of numbers to a binary heap in $\Theta(n)$ time?

$\endgroup$
1
  • $\begingroup$ Why does this seem pessimistic? How many comparable data structures do you know where the time for creating one with $n$ elements is asymptotically smaller than inserting $n$ elements? $\endgroup$
    – Raphael
    May 4, 2014 at 10:21

1 Answer 1

4
$\begingroup$

Wikipedia claims that insertion takes $O(1)$ amortized time, and so converting an array of numbers into a binomial heap should indeed take time $O(n)$. This is also supported by these lecture notes, and probably mentioned in CLRS.

$\endgroup$
3
  • $\begingroup$ Thank you! But now I'm wondering if there was a way to modify the original heap/algorithm to get similar results, without the use of amortized analysis? $\endgroup$
    – user119264
    May 3, 2014 at 16:11
  • $\begingroup$ @Yuval The structure of binomial heaps has familiarities to the binary numbers. Adding one to a binary number costs $O(\log n)$ (since in the worst case all bits change) but counting up to $n$ amortizes these numbers. It is my intuition that the same happens in binomial heaps. Bad news: the third edition of CLRS dropped the binomial heaps. $\endgroup$ May 3, 2014 at 16:32
  • 3
    $\begingroup$ @user119264 Amortised analysis does not make changes to the structure. $\endgroup$
    – Raphael
    May 4, 2014 at 10:22

Your Answer

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

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