Queues Top Binary Trees Contents

Priority Queues

Synopsis

Abstractly, a priority queue is an ordered list of elements. Inserting into a priority queue entails placing the new element in its proper position to maintain the ordering. Thus, the point of the insertion can be anywhere in the list: front, interior, or back. Removing from a priority queue means removing an extreme element, either the `smallest' or the `largest'. An auxiliary value, called a rank, is used to decide which element is the smallest or largest.

A priority queue is neither a stack nor a queue, but is similar to both. Both a stack and a queue order their elements by the insertion time, whereas a priority queue orders its elements by their ranks. Here is an example:

    pq = new PriorityQueue();
    pq.enqueue("alpha",3);        //element first, rank second
    pq.enqueue("beta",2);
    pq.enqueue("gamma",4);
    pq.enqueue("delta",1);

At this point, the ordered list of elements would be:

    ("delta","beta","alpha","gamma")

Typically, but not always, the smallest rank is the highest priority, so a removal (dequeuing) would remove the element "delta".

Structure

Generally, the structure of a priority queue resembles that of a queue or a stack.

Vocabulary

The terms used in describing a priority queue are:

enqueue
The name of the operation that adds an element, with a given rank, to a priority queue.
dequeue
The name of the operation that removes the element with the smallest (largest) rank. Usually, the element removed is returned by the dequeue operation, with the rank being thrown away.
peek
Like dequeue, but the element is not removed from the queue. Consecutive peeks, with no intervening enqueues or dequeues, always return the same element.
rank
The value used to order the elements in a priority queue. Each element is associated with a rank.
priority
Another name for rank.
first-come-first-served
A strategy for dealing with the insertion of an element with the same rank as a previously enqueued, but not yet dequeued, element. Under this strategy, the newly inserted element should be dequeued after the previously enqueued element.

Supports

Priority queues are used in some important graph algorithms as well as in discrete-event simulations.

A priority queue, where the rank of an insertion is forced to be greater than the rank of the previous insertion implements a stack. In such a case, the last element inserted has the highest rank and thus is the next element to come off the priority queue. Conversely, forcing the rank of an insertion to be less than that of the previous insertion implements a queue.

Dependencies

Priority queues are often built from singly-linked lists or heaps. If the priority queue is based upon a linked-list, a tail pointer is not needed (although if present, it can provide a significant optimization if enqueues generally end up at the back of the list).

Operations

The operations of a priority queue have the same name as the operations of a queue, namely enqueue, dequeue, peek, and isEmpty. Of course, the enqueue operation takes a rank as well as the element to be enqueued.

The enqueuing operation can take anywhere from constant to linear time, depending on the underlying data structure used to implement the priority queue. The dequeuing operation can take anywhere from constant to logarithmic time, again depending on the underlying structure. The choice of the underlying structure depends on whether one wishes for faster enqueues (at the cost of slower dequeues) or vice versa.

Traversals

Priority queues are generally not traversed.

Concept Inventory

     
  1. This is a question.
    1. This is one possible answer
    2. This is another possible answer

lusth@cs.ua.edu


Queues Top Binary Trees Contents