Binary Heaps: Heapify and Build-Heap

A binary heap is a complete binary tree stored in an array; MAX-HEAPIFY repairs one node by sifting it down in $\Theta(\lg n)$, while BUILD-MAX-HEAP turns an unordered array into a heap bottom-up in $\Theta(n)$ — not $\Theta(n\lg n)$.