Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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? –  user119264 May 3 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. –  Hendrik Jan May 3 at 16:32
3  
@user119264 Amortised analysis does not make changes to the structure. –  Raphael May 4 at 10:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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