Priority Queue

Priority Queues

If the queue is implemented on the basis of the intrinsic order of elements (eg: numeric, alphabetical order etc.), then the queue is called priority queue.

The elements in the priority queue need not be numbers, characters but can also be complex data structures that are ordered on one or several fields.

Sometimes, the PQ can also be defined via a special, external value which is not even part of elements themselves. For eg: stack—descending priority whose elements are ordered during the time of insertion. Similarly, a queue is an ascending priority queue.

Types:

• Ascending PQ:Items can be inserted arbitrarily but from which only the smallest item can be removed.
• Descending PQ:Insertion is done arbitrarily but only the largest item is removed first.

Insertion in PQ is same as in non-priority queues.

Deletion requires a search of highest priority element and deletion of the element is done. Two elements with the same priority are processed according to the order in which they were added to the queue.

A priority queue must at least support the following operations:

• insert_with_priority: add an element to the queue with an associated priority.
• pull_highest_priority_element: remove the element from the queue that has the highest priority, and return it.

References:

1. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structuresusing C and C++”

2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction to Algorithms”

3. G. Brassard and P. Bratley, “Fundamentals of Algorithms”

4. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program designin C”