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.