9.2.1 Simple Implementations

To implement a priority queue, first represent its objects and priorities as records with priority fields. Two ways to store the records come immediately to mind. The records can be stored in an array or in a list. In either case, the programmer may choose to store the records in arbitrary order or in order of priority. Table 9.1 gives the worst-case insertion and deletion times for each of the four resultant implementations, when n records are present in the priority queue. For example, when using the ordered array implementation, the top array record will have highest priority; thus deletion can be performed in constant time by using a pointer top to the current top record. Insertion of a record requires a search of the array to find its proper position. A binary search will allow this position to be found quickly, but to insert it requires O(n) time, because all records below it must be shifted down.

Table 9.1 Worst-Case Insertion and Deletion Times for the Priority Queue

           Implementation  Insertion  Deletion

----------------------------------------------

           Array           Constant   O(n)

Unordered  List            Constant   O(n)

           Array           O(n)       Constant

Ordered    List            O(n)       Constant

The table shows that if insertions are more frequent than deletions, it is better to use unordered records. In addition to considering the time for insertion and deletion, the amount of storage required for the list and array implementations must be evaluated. Arrays take less storage.