USING C++

A priority queue is an abstract data type for storing a collection of prioritized elements that supports arbitrary element insertion, but supports removal of elements in order of priority, that is, the element with first priority can be removed at any time.

The Priority Queue ADT

As an ADT, a priority queue P supports the following functions:

isPQueueEmpty(): returns true if pqueue is empty otherwise false

size(): Return the number of elements in P.

empty(): Return true if P is empty and false otherwise.

insert(e): Insert a new element e into P.

min(): Return a reference to an element of P with the smallest associated key value (but do not remove it); an error condition occurs if the priority queue is empty.

removeMin(): Remove from P the element referenced by min(); an error condition occurs if the priority queue is empty.

Example : The following table shows a series of operations and their effects on an initially empty priority queue P. Each element consists of an integer, which we assume to be sorted according to the natural ordering of the integers. Note that

each call to min returns a reference to an entry in the queue, not the actual value. Although the Priority Queue column shows the items in sorted order, the priority queue need not store elements in this order.

Operation Return Priority Queue

insert(5) {5}

insert(9) {5,9}

insert(2) {2,5,9}

insert(7) {2,5,7,9}

min() [2] {2,5,7,9}

removeMin() [2] {5,7,9}

size() 3 {5,7,9}

min() [5] {5,7,9}

removeMin() [5] {7,9}

removeMin() [7] {9}

removeMin() [9] {}

empty() true {}

removeMin() invalid operation {}

Implementing a Priority Queue with a List

In this section, we show how to implement a priority queue by storing its elements in an Linked list. We may consider two realizations, depending on whether we sort the elements of the list.

1. Implementation with an Unsorted List

Let us first consider the implementation of a priority queue P by an unsorted linked list L. A simple way to perform the operation insert(e) on P is by adding each new element at the begining of L. This implementation of insert takes O(1) time.

Since the insertion does not consider key values, the resulting list L is unsorted. As a consequence, in order to perform either of the operations min or removeMin on P, we must inspect all the entries of the list to find one with the minimum key value. Thus, functions min and removeMin take O(n) time each, where n is the number of elements in P at the time the function is executed.

2. Implementation with a Sorted List An alternative implementation of a priority queue P also uses a list L, except that this time let us store the elements sorted by their key values. Specifically, we represent the priority queue P by using a list L of elements sorted by nondecreasing key values, which means that the first element of L has the smallest key. We can implement function min in this case by accessing the element associated with the first element of the list L. Likewise, we can implement the removeMin function of P by removing first node of list L. Assuming that L is implemented as a linked list, operations min and removeMin in P take O(1) time, so are quite efficient.

Following table compares the running times of the functions of a priority queue realized by means of an unsorted and sorted list, respectively. There is an interesting contrast between the two functions. An unsorted list allows for fast insertions but slow queries and deletions, while a sorted list allows for fast queries and deletions, but slow insertions.

Operation Unsorted List Sorted List

size, empty O(1) O(1)

insert O(1) O(n)

min, removeMin O(n) O(1)