# Creating a binomial heap from an array in Θ(n) time

I'm studying binomial heaps. A book tells me that insertion of a node to a binomial heap take $\Theta(\log n)$ time. So given an array of $n$ elements it would take $\Theta(n \log n)$ time to convert it to a binomial heap.

Does anyone know a method that can convert an array of numbers to a binomial heap in $\Theta(n)$ time? Wikipedia claims that insertion takes $O(1)$ amortized time but I need to refer to the worst case.

$O(f(n))$ amortized time means that if we make $k$ consecutive operations, total time does not exceed $k \cdot cf(n)$ for a chosen positive constant $c>0$.

In your case, each insertion is worst-case $O(\log n)$. However, they're amortized $O(1)$. It means that if you make $n$ consecutive insertions (that is, build a heap from an array), total time is bounded by $c \cdot n$ for some constant $c>0$ - that is, the total time is $\Theta(n)$.

If you want to prove formally that the total time of constructing $n$-element heap is $\Theta(n)$:

• Denote $k$ as the current number of items in our heap (in the beginning, $k=0$).
• Write $k$ in binary; if its $i$-th bit is set, we have a binomial tree of size $2^i$.
• If you insert next element when there are already $k$ of them, you create a new tree of size $2^0$; if there was already a heap of size $2^0$, you merge them into a heap of size $2^1$; if there was already a heap of size $2^1$, you merge them and so on, until you find out there was no heap of size $2^t$ in a previous state. Time needed is thus proportional to the number of ones in the end of binary representation of $k$ (plus 1).
• Note that we make first heap for every $k$; we'll make the second heap for each odd $k$, third heap for each $k \equiv 3 \mod{4}$ and so on. It means that $i$-th operation inside "merge-heap" will be done roughly once in $\frac{n}{2^i}$ insertions.

Now note that number of (constant time) create-tree/merge-tree operations cannot exceed $$\frac{n}{2^0} + \frac{n}{2^1} + \frac{n}{2^2} + \dots = 2n.$$

Thus, the total time for the algorithm "just make $n$ consecutive insertions" is $\Theta(n)$.

The answer given above by mnbvmar is fine. Just want to add one thing. Total number of create-tree/merge-tree operations cannot exceed $$\frac {n}{2^0} + \frac{n}{2^1} + \frac{n}{2^2} + \dots +\frac{n}{2^{\lfloor \log n\rfloor}}\,.$$

Now we can rewrite the expression as $$n \left(\frac {1}{2^0} + \frac{1}{2^1} + \frac{1}{2^2} + \dots +\frac{1}{2^{\lfloor \log n\rfloor}}\right)\,.$$ The series inside the brackets converges to constant 2. So the running time of the algorithm is $O(n)$.