Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 7

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.

The central behavior is $\boxed{\mathrm{maximum}(Q)\in \underset{x\in Q}{\mathrm{argmax}}\mathrm{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.

Store a complete binary tree in an array $H[\mathrm{0..}n)$, with children $2i+1,2i+2$ and parent $\lfloor (i-1)/2\rfloor$. The max-heap invariant says every parent's key is at least its children's keys. Consequently the root is a greatest-key item, and the height is $\lfloor {\log }_{2}n\rfloor$.

Here is a pairwise-exchange implementation of extractMax:

extractMax(H, n):
    if n == 0: error "empty priority queue"
    answer = H[0]
    swap(H[0], H[n-1])
    n = n - 1
    i = 0
    while 2*i + 1 < n:
        j = 2*i + 1
        if j + 1 < n and key(H[j+1]) > key(H[j]):
            j = j + 1
        if key(H[i]) >= key(H[j]): break
        swap(H[i], H[j])
        i = j
    return (answer, n)

Only the root can initially violate heap order. Each heapify down exchange promotes the larger child, making the previous position valid and moving the only possible violation down one level. It either stops at a valid position or reaches a leaf. The removed root is saved as answer, and reducing the active array length preserves the complete binary tree shape.

The binary heap operation costs, with existing positions available for handle operations, are:

Insertion into the binary heap places an item at the next leaf and moves it upward until heap order holds. Raising a key uses the same upward repair. Arbitrary deletion replaces its position by the final item and repairs upward or downward as necessary. A handle must be updated on exchanges; locating an item by value alone can require linear search. The boxed main bounds are $\boxed{\mathrm{maximum}:O(1),\mathrm{insert},\mathrm{extractMax}:O(\log (n+1))}$. Dynamic array resizing is usually amortized or avoided by reserving sufficient capacity.

Count pairwise exchanges in the implementation from part (b), including the initial root/final-leaf exchange. For $n\ge 4$, the final leaf has a nonroot parent whose key is strictly larger than the leaf's key. That parent remains after deletion. If the moved leaf could stay at the root without a downward exchange, it would dominate both root children and hence every remaining descendant, contradicting that larger remaining parent. Thus at least one heapify down exchange is necessary.

One downward exchange suffices. The following level-order array is a max-heap on keys one through fifteen:Every parent is larger than both children. Exchange the root key fifteen with the final key ten, remove fifteen, then exchange ten with the larger root child fourteen. Ten now has children nine and eight, so repair stops. The final array is

Hence the best-case maximum deletion in a binary heap isThis best case can be arranged at any such size: make the root child on the opposite side from the old final leaf the largest remaining key, the old leaf smaller than its own ancestors but larger than all descendants of that opposite child, and fill the remaining positions in decreasing order along each branch. The promoted child then allows the leaf to stop at depth one.

For sizes two and three, one initial exchange can suffice; for size one no exchange between distinct positions is needed. If only exchanges during heapify down are counted, the answer for $n\ge 4$ is one. In the fifteen-key example the two exchanges involve three distinct keys, namely fifteen, ten and fourteen. An implementation that moves a hole by assignments need not perform literal swaps, so the count is explicitly tied to the exchange implementation. The worst-case time complexity remains logarithmic even though this best-case repair is constant.

Assume $1\le k\le n$. Use bottom-up heap construction to make a max-heap of the first $k$ input items. For each subsequent input value $x$, compare it with the root. If $x$ is at least the root, discard it; otherwise replace the root by $x$ and apply heapify down. Return the final root.

The loop invariant says the heap contains a multiset of the $k$ smallest values seen so far. It holds after initialization. If $x$ is at least the current largest retained value, the already retained $k$ items are no larger, so discarding $x$ preserves the invariant. If $x$ is smaller, remove one largest retained value and keep $x$ instead; precisely the $k$ smallest values remain. This argument handles equal integers by treating repeated occurrences as separate items. At the end,Construction costs $O(k)$; each remaining value uses one comparison and at most one logarithmic repair. Thus the selection algorithm has time complexityFor $k=1$, the heap is a single running minimum and the time is $O(n)$. The uniform expression $O(n\log (k+1))$ covers that boundary; interpreting the printed $O(n\log k)$ literally at $k=1$ would incorrectly make it zero.