Codelogn: Heap Sort in Big O

Keys

1. add(x) and remove(x) are O(log n).

2. The height of the heap is

\left\lfloor \lg (n) \right\rfloor

3. The number of nodes at height

h

\le \left\lceil 2^{\left(\lg n - h\right) - 1} \right\rceil = \left\lceil \frac{2^{\lg n}}{2^{h+1}}\right\rceil = \left\lceil\frac{n}{2^{h+1}}\right\rceil

4. The cost of heapifying all subtrees is: (Sum of step-3 against each height)

$\begin{align} \sum_{h=0}^{\lceil \lg n \rceil} \frac{n}{2^{h+1}}O(h) & = O\left(n\sum_{h=0}^{\lceil \lg n \rceil} \frac{h}{2^{h + 1}}\right) \\ & \le O\left(n\sum_{h=0}^{\infty} \frac{h}{2^h}\right) \\ & = O(n) \end{align}$

* uses the fact that the given infinite series h / 2^h converges to 2.

Reference

http://opendatastructures.org/versions/edition-0.1e/ods-java/10_1_BinaryHeap_Implicit_Bi.html

http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation

Codelogn

Tuesday, May 13, 2014

Heap Sort in Big O

No comments:

Post a Comment