Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming / 5 / b / iii

A minimum-oriented binary heap is an appropriate alternative. Store a complete binary tree in an array and maintain heap order. Insertion appends a value and moves it upward; removing the root replaces it by the last value and moves that value downward. Each path has $O(\log (n+1))$ levels, and equal values can be stored in separate slots. Both operations therefore take $O(\log (n+1))$ time when capacity is available.

Unlike a binary search tree, the heap does not maintain a complete search order, so finding an arbitrary specified value can require $O(n)$ inspections. A simple array implementation also has a capacity issue: a fixed array can fill, and resizing a growable array occasionally costs $O(n)$, giving an amortized insertion guarantee unless allocation is otherwise managed. This capacity cost is an implementation tradeoff, not an inherent inability of heaps to represent the priority queue abstraction.