2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.