= Solution
A <maximum priority queue> is an <abstract data type> holding items with comparable priority keys and giving access to a greatest-key item. Equal priorities may occur; any one of the tied maximum items can be returned unless a tie rule is specified.
* `empty` or initialization creates a queue with no items; `isEmpty` and `size` inspect its occupancy.
* `insert(item, key)` adds an item with its priority.
* `maximum()` returns a greatest-priority item without removing it.
* `extractMax()` returns and removes a greatest-priority item.
* When mutable priorities are supported, `increaseKey(handle, newKey)` raises an existing item's priority; the handle identifies its stored location.
The central behavior is $\boxed{\operatorname{maximum}(Q)\in\operatorname*{arg\,max}_{x\in Q}\operatorname{key}(x)}$. Calling `maximum` or `extractMax` on an empty queue must report that no item exists. Raising a key is a common supported extension; arbitrary-key changes and deletion by handle can also be supplied.
Back to article page
