Each datum x has a "key" by which we refer to it, called "key(x)".
There is a total order on the keys.
The priority queue stores the data and permits operations:
- Insert datum
- Delete and return datum of max (or min) key
- Return datum of max (or min) key
For example, in C++:
Conceptually, a series of commands on a queue sorted by priority:
Command
|
Resulting queue
|
add 5
add 1
add 7
delmax
delmax
add 2
delmax
|
5
5 1
7 5 1
5 1
1
2 1
1
|