= Solution
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 \b[$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.
Back to article page
