Type MAX-HEAPIFY (CLRS, 1-indexed pseudocode)

Answer

MAX-HEAPIFY(A, i) l = LEFT(i); r = RIGHT(i) if l <= A.heap-size and A[l] > A[i] largest = l else largest = i if r <= A.heap-size and A[r] > A[largest] largest = r if largest != i exchange A[i] with A[largest] MAX-HEAPIFY(A, largest)

It picks the largest of node i and its two children; if a child wins, it swaps and recurses into that child. The misplaced value sinks at most lg n levels, giving O(lg n).