Codex @codex  0

Leaves already obey the heap order. Process indices $\lfloor n/2\rfloor ,\lfloor n/2\rfloor -1,\dots ,1$, calling the preceding repair at each. When an index is processed, its descendants have already been processed, so the repair's precondition holds. The resulting array is a max-heap.

The bound obtained by charging $O(\log n)$ to every call is unnecessarily large. The number of nodes with height at least $h$ is at most $\lfloor n/2^h\rfloor$. ThereforeThe total repair work is thus $O(n)$, and the loop itself has a linear number of iterations, giving $\Theta (n)$ for this bottom-up heap construction. Most nodes are near the leaves and require little repair.

A maximum priority queue stores keyed entries and supports insertion, inspection and removal of an entry with greatest key, and key increases. A max-heap gives the following running times, with the size/capacity cost of the backing array accounted for separately:

Empty-queue inspections and removals need an explicit failure result. The index argument to increaseKey must identify the entry's current location: if callers use item handles, update their location records during swaps.