### *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: