The (binary) heap data structure is an array object that we can view as a nearly complete binary tree.
although A[1 .. A: length] may contain numbers, only the elements in A[1..A:heap-size], where 0 <= A:heap-size <= A:length, are valid elements of the heap.
max-heap: A[PARENT(i)] >= A[i]
height is Θ(lg n)
MAX-HEAPIFY(A,i) //heapify a specific node (move it down tree if necessary) 1 l = LEFT(i) 2 r = RIGHT(i) 3 if l <= heap-size[A] and A[l] > A[i] 4 then largest = l 5 else largest = i 6 if r <= heap-size[A] and A[r] > A[largest] 7 then largest = r 8 if largest != i 9 then exchange A[i] <-> A[largest] 10 MAX-HEAPIFY(A,largest)
because a = 1 then nlogba becomes O(1), therefore ti is equal to f(n), hence O(1* lg n)
Heap-Sort: Build maxheap O(lg n) + traverse (n lg n) => O(n lg n)