Priority queue ADT
In practice we often deal with priorities. For instance, in a to-do-list for a day, each task has an associated significance. Is absolutely necessary to collect a car from repair shop (highest priority) and you may possibly watch a new film (lowest priority). Besides real life examples, many computer tasks work with priorities. Frequently cited instance is the Dijkstra's shortest path algorithm. Priority queue ADT lets us to work with objects that have an associated priority.
In the application we have a pair (priority, item) where an item is some auxiliary data priority is associated with. To maintain simplicity, we omit priorities and consider that for items e1, e2: e1 < e2 means e1 has higher priority than e2.
Operations
- PriorityQueue create()
creates empty priority queue
- boolean isEmpty(PriorityQueue pq)
tells whether priority queue pq is empty
- insert(PriorityQueue pq, Item e)
inserts item e to priority queue pq
- Item minimum(PriorityQueue pq)
tells minimal item in priority queue pq
Precondition: pq is not empty
- removeMin(PriorityQueue pq)
removes minimum item from priority queue pq
Precondition: pq is not empty
- destroy(PriorityQueue pq)
destroys priority queue pq
Implementations
Recommended books
- Cormen, Leiserson, Rivest. Introduction to algorithms. (Theory)
- Robert Lafore. Data Structures and Algorithms in Java. (Practice)
- Mark Allen Weiss. Data Structures and Problem Solving Using C++. (Practice)
Contribute to AlgoList
Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.
Every dollar helps!