UNC-CH COMP 410

Priority Queue of int: Axiomatic definition

Here we discuss the ADT called a "priority queue" (PQUE). The basic ADT allows a few main operations: 

   insert: PQUE x E  --> PQUE
   getMin: PQUE      --> E     where E is the smallest item in the queue
   delMin: PQUE      --> PQUE  where the smallest item has been removed
We traditionally call this a queue but in its simplest form it is just a collection with a way to find/remove the smallest element. Some formulations may add queue-like behavior (such as if two items have the same value/priority, then the "smallest" is the one first inserted into the PQUE).

There are 2 versions we will discuss.

Version given in your text

Here, the idea of "priority" is mixed with the element in the PQUE; the elements are thought of as directly being items that can be ordered (int, string, etc).

This is a simplification (but then, we are dealing with an abstraction). Normally, we want to put things like processes in the PQUE, so the data item would be tagged with something orderable, like an integer priority level.

Alternate version

This is not really different in terms of what can be done with it. Rather, it is presented with the concept of "priority" separated from the element itself.

Since the integer priority is a separated data element i this version, we have made the axioms more generic. Here is the definition of a PQUE that allows elements of any type: