# Can we create binomial heaps in linear time?

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?

• 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?
– Raphael
May 4 '14 at 10:21

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.

• 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? May 3 '14 at 16:11
• @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. May 3 '14 at 16:32
• @user119264 Amortised analysis does not make changes to the structure.
– Raphael
May 4 '14 at 10:22