Binary Heap and Binomial Heap

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

About

Search

PISIKA Copyright © 2009