• Max-heapify: O(log n), maintains max-heap property
• build-max-heap: O(n log n), from unordered to max heap
• Heap Sort: O(n log n), sort in place
• Max-heap-insert, extract, increase-key, maximum; O(log n): to implement a priority queue

Max hepify

Makes A(i) float down.

Assumptions:

• L(i), R(i) are max-heaps
• A(i) may be smaller than children (violates property)

maxHeapify(A, i)
    // O(log n)
    l = left(i);
    r = right(i);
    if (l <= A.size && A[l] > A[i]) {
        largest = l;
    } else {
        largest = i;
    }
    if (r <= A.size && A[r] > A[largest]) {
        largest r;
    }
    if largest != i {
        swap (A[i], A[largest]);
        maxHeapify(A, largest);
    }

Build Max Heap

We can use maxHeapify to bottom-up build a heap

buildMaxHeap(A) {
    // O(n log n)
    A.size = A.len;
    for i = floor A.len / 2 to 1 {
        // O(n)
        maxHeapify(A, i); // O(log n)
    }
}