Heapify(array \(A\) with size \(N\), index \(i\) that contains node \(n\)):
Assuming subtrees of node \(n\) are max heaps.
- Idea: correcting one violation of heap invariant at \(n\). Swap \(n\) with one of its child and recursively call Heapify on that child.
It can be easily derived that
- Number of levels below \(n\): \(L = \lceil \lg{\frac{N}{i}} \rceil = \lceil \lg{N} - \lg{i} \rceil\)
Let \(T_{Heapify}(L)\) be the time complexity. We have the simple recurrence relation:
\[\begin{cases} T_{Heapify}(L) = T_{Heapify}(L - 1) + O(1) \\ T_{Heapify}(0) = 0 \end{cases}\]Therefore, \(T_{Heapify}(N, i) \in O(\lg{N} - \lg{i})\)
Build_max_heap(Array \(A\) with size \(N\)):
- Idea: the second half of a heap is consisted of leaves. So constructing a heap is calling Heapify from bottom to top on all of the nodes.
Without loss of generality, assume \(N\) is a power of 2. Let \(T(N)\) be the time complexity.
Pseudocode (note that here the heap starts from index 1):
1
2
for i in range(N/2, 1):
Heapify(A, i)
Heap_sort(Array \(A\) with size \(N\)):
- Idea: after popping out the first (max or min) element, move one of the leaves to \(A[1]\) and call Heapify(\(A\), \(1\)). Continue to do so and get a sorted list.
Let \(T(N)\) be the time complexity.
\[\begin{array} {lcl} T_{Heap\_sort}(N) & = & \sum_{i = 2}^{N - 1} T_{Heapify}(i, 1) \\ & = & \sum_{i = 2}^{N - 1} O(\lg{i}) \\ & \leqslant & O(\int_{2}^{N} \lg{x} dx) \\ & \leqslant & O(N \lg{N} - N - (2 \lg{2} - 2)) \\ & \in & O(N \lg{N}) \end{array}\]