Binary Heaps: Invariants, Linear-Time Build-Heap & Heap Sort

A Binary Heap is a complete binary tree stored as an array without explicit pointer overhead:

- The tree is completely filled on all levels except possibly the lowest, which is filled from left to right.

- For node at index i (1-indexed):

text{Parent}(i) = lfloor i / 2 rfloor, text{Left}(i) = 2i, text{Right}(i) = 2i + 1.

Heap Property:

- Max-Heap: A[text{Parent}(i)] >= A[i]. The maximum key is always at index 1.

- Min-Heap: A[text{Parent}(i)] <= A[i]. The minimum key is always at index 1.

To build a heap from an unordered array of n elements:

Call Max-Heapify bottom-up from index lfloor n/2 rfloor down to 1.

Mathematical Derivation:

- An n-element heap has height lfloor log_2 n rfloor.

- There are at most lceil n / 2^{h+1} rceil nodes at height h.

- Running Max-Heapify on a node of height h takes O(h) time.

Total time:

T(n) <= sum_{h=0}^{lfloor log_2 n rfloor} lceil frac{n}{2^{h+1}} rceil * O(h) <= frac{n}{2} sum_{h=0}^infty frac{h}{2^h}

The infinite arithmetic-geometric series sum_{h=0}^infty frac{h}{2^h} = 2.

Therefore: T(n) <= frac{n}{2} * 2 = O(n).