Relation: implicitly defined linear ordering

An Abstract Priority Queue is defined on objects linearly ordered by a value called the priority. We will assume that the priority is a nonnegative integer with highest priority going to the smallest value.

Critical Operations for Abstract Priority Queues

• Insert a new object
  void push( Type, priority ) const;
• Examine the head of the priority queue
  Type top() const
• Remove the object at the head of the priority queue
  void pop()

By restricting the relevant operations, it is possible to make significant improvements in the run times.

Example Data Structures

The most common data structure for implementing a priority queue is the binary heap. In this case, top is O(1), push has an average-case O(1) run time, and pop is O(ln(n). Almost all other operations on implicit linearly ordered lists, however, are now O(n).

A N-ary heap is also possible with the same run times as a binary heap.

If other operations are necessary, an AVL tree will still be acceptable; however, the three operations now all be O(ln(n)).

If merging two priority queues is also flagged as a critical operation, a leftist heap has O(n) run time for push, pop, and for merging two leftist heaps.

Another data structure similar to a leftist heap is a skew heap. While the author has not investigated this, it has been claimed that skew heaps are better on average than leftist heaps.