= Solution
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:
* `maximum`: return the root key in \b[$O(1)$] time.
* `insert`: append at the next available leaf, then use <sift up> until the <heap order> holds, in \b[$O(\log n)$] time.
* `extractMaximum`: save the root, replace it by the last entry, reduce the size, and use <sift down>, in \b[$O(\log n)$] time.
* `increaseKey(i,k)`: reject $k<A[i]$; otherwise set the new key and use <sift up>, in \b[$O(\log n)$] time.
* `isEmpty` and `size`: inspect the stored size in \b[$O(1)$] time; construct a queue from $n$ keys by <bottom-up heap construction> in \b[$\Theta(n)$] time.
Empty-queue inspections and removals need an explicit failure result. The index argument to `increaseKey` must identify the entry's \i[current] location: if callers use item handles, update their location records during swaps.
Back to article page
