[Solved]: Creating a binomial heap from an array in Θ(n) time

$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)$.