= Solution
The abstract state is a finite <multiset> $Q$ of ordered values, initially empty. Multiplicity matters: deleting the minimum removes one occurrence, not every equal occurrence. Assume a consistent <total order> on `T`.
``
trait PriorityQueue[T] {
// Pre: true. Post: Q' is the empty multiset.
def clear(): Unit
// Pre: true. Post: Q' = Q with one additional occurrence of x.
def insert(x: T): Unit
// Pre: Q is nonempty.
// Post: result is a minimum of Q;
// Q' is Q with exactly one occurrence of result removed.
def delMin(): T
// Pre: true. Post: result iff Q is empty, and Q' = Q.
def isEmpty(): Boolean
}
``
This <abstract data type> places no fixed-capacity bound on insertion. \b[The only operation requiring a nonempty collection is `delMin`]. The representation must preserve duplicates even if it uses a <data structure> commonly associated with <sets>.
Back to article page
