Definition

A priority queue is a data structure of items with keys that supports two basic operations:

• insert a new item
• delete the item with the largest key

Background

It is similar to Queues (delete the oldest) and Stacks (delete the newest), but their effecient implementation is more challenging. The priority queue is a proper generalization of the stack and queue, because data structures can be implemented with them.

Any priority queue can be used as the basis of a sorting algorithm by inserting all the records, the successively removing the largest to get the records in reverse order.

In practiver they are more complex than the definition given, as ther are severl other operations that may be needed to perform to maintain them under all the conditions that migh arise when being used. The flexibility in allowing client programs to perform a variety of different operations on sets of records with keys is why they are so useful.

Operations

We want to build and mainatin a structure containing records with numerical keys (priorities) that supports some of the following operations:

• Construct a priority queue from \(N\) given items
• Insert a new item
• Delete the maximum item
  • If records have duplicate keys, the “maximum” means “any record with the largest key value”.
• Change the priority of an arbitrary specified item
• Delete an an aribitrary specified item
• Join two priority queue into on large one

In adiiton to stanard initialize, test empty, destroy, and copy ops.

References:

• Algorithms in C, Robert Sedgewick