HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

Can we create binomial heaps in linear time?

Submitted by: @import:stackexchange-cs··
0
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.