Problem Detail: 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(nlog 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?
Asked By : user119264
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/24355
