**Problem:**

[1.] Show how to create a Binary Heap in $O(n)$ steps.

[2.] Show how to create a Binomial Heap in $O(n)$ steps.

**Solution:**

**[1.] Binary Heap**

A binary heap of size $n$ could be created by successive insertions. This approach however requires $O(n\lg n)$ steps

because each insertion takes $O(\lg n)$ time and there are $n$ elements. We can however do it in a more optimal fashion

so that it will only require $O(n)$ steps.

The optimal method starts by arbitrarily putting the elements on a binary tree, respecting the shape property. Then starting

from the lowest level and moving upwards, shift the root of each subtree downward until the heap property is restored. This

process takes $O(h)$ swaps per node, where $h$ is the height of that node. Since, the number of nodes at height $h$ is at most

$\frac{n}{2^{h+1}}$.

The cost of building a binary heap using this optimal method is:

$\sum\limits_{h=0}^{\lg n}\frac{n}{2^{h+1}}h$

$= (n\sum\limits_{h=0}^{\lg n}\frac{h}{2^{h}})$

$\leq O(n\sum\limits_{h=0}^{\infty}\frac{h}{2^{h}})$

$\leq O(2n)$, since $\sum\limits_{h=0}^{\infty}\frac{h}{2^{h}}=2$

$= O(n)$

**[2.] Binomial Heap**

A binomial heap of size $n$ could be created by $n$ successive insertions. The amortized cost of insert is $O(1)$,

thus the cost of building a binomial heap using this method is

$nO(1) = O(n)$

You can also see explicitly as discussed in class. Inserting a sequence of $n$ nodes takes this much steps,

$(n/2)(1) + (n/4)(2) + (n/8)(3) + (n/16)(4) + . . . $

$\leq n\sum\limits_{h=0}^{\infty}\frac{m}{2^{m}} = 2n = O(n)$