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$
  • $\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 '14 at 10:21
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$
  • $\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 '14 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$ – Hendrik Jan May 3 '14 at 16:32
  • 3
    $\begingroup$ @user119264 Amortised analysis does not make changes to the structure. $\endgroup$ – Raphael May 4 '14 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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