|
Introduction
Syllabus
Guidelines for labs
Lab sections
Take quiz & check grades
| |
Priority Queue
A priority queue is an abstract type so that you can insert and remove items.
 | Each item or record contains a field that determines the priority of that record |
| You always remove the item with the highest priority |
| In some situations the priority is expressed in increasing order, so you remove the
item with the lowest priority value. |
Uses of priority queues:
| Task scheduling: always schedule task with highest priority |
| Simulation: Examine the event that will happen first |
What is involved?
Keep records sorted by priority:
| linear array - slow insertion, slow removal |
| linked list - slow insertion, fast removal |
| heap - good insertion and removal |
|