snippetMinor
Can we create binomial heaps in linear time?
Viewed 0 times
canlinearcreatetimebinomialheaps
Problem
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?
Solution
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.
Context
StackExchange Computer Science Q#24355, answer score: 4
Revisions (0)
No revisions yet.