# 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 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.
@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. –  Hendrik Jan May 3 at 16:32