GENERIC INTERFACEPQueueRep (PQ);
where PQ = PQueue(Priority).
REVEAL PQ.Default <: DefaultPub;
TYPE
EltsArray = REF ARRAY OF PQ.Elt;
DefaultPub = PQ.DefaultPub OBJECT
sz: CARDINAL := 0; (* number of elements in heap *)
heap: EltsArray := NIL; (* elements stored in heap[1..sz] *)
END;
END PQueueRep.
A PQueue.Default is represented by a data structure called a {\it heap}.
A heap is a complete binary tree in which each node has a priority at least
that of its parent. Hence, the root of the tree has minimal priority.
A priority queue pq: PQueue.Default is {\it valid} (written Valid(pq))
iff pq.heap # NIL. The methods init(pq, sizeHint) and fromArray(pq,
e) establish Valid(pq), and all of the other methods beside pCompare
require Valid(pq).
A valid priority queue pq: PQueue.Default satisfies the following
invariants:
1. 0 <= pq.sz <= LAST(pq.heap^)
2. (forall i: 1 < i <= sz: pq.pCompare(pq.heap[i DIV 2], pq.heap[i]) < 1)
The heap is represented by an array pq.heap, and a count pq.size of the
number of elements in the heap. The pq.size elements are stored in the
array entries pq.heap[1] through pq.heap[pq.size]. The element
pq.heap[1] is the root of the heap, and the parent of element i is the
element i DIV 2. The second invariant is the heap invariant: the priority
of a non-root element is at least that of its parent.
For a complete description of priority queues, see Algorithms in
Modula-3, Robert Sedgewick, Addison-Wesley Publishing Company, 1993,
Chapter 11.