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 / b

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.