Priority Queue

A priority queue is a collection of elements, in which each element has been assigned a priority value. The order in which the elements will be processed is decided by the priority of the element.

  • An element with higher priority is processed first.
  • If elements with the same priority occur, they are processed according to the order in which they were added to the queue.

Usually, a lower priority number means higher priority.

Representation of Priority Queue

Priority queue can be represented using an array or a linked list.

Linked Representation of Priority Queue

When a priority queue is implemented with a linked list, each node will contain three parts:

  • Data.
  • The priority number of the element (PRN).
  • The address of the next element.

Following is an example of a linked representation of a priority queue.

Linked Representation of Priority Queue
Linked Representation of Priority Queue

It has 4 elements A, B, C, D having priority 1, 2, 2 and 3 respectively. Here A will be processed first since it has a higher priority. Elements B and C has the same priority and we can say that B was inserted in the queue before C.

Inserting a new element in a linked priority queue

  • Traverse the list until finding a node PTR with a lower priority than the new element.
  • Insert new element in front of the node PTR.

Consider the following linked priority queue where we have to insert a new element S having priority 4.

Inserting a New Element in a Linked Priority Queue
Inserting a New Element in a Linked Priority Queue

If an element with the same priority as the new element already exists, the new element is put after that element.

Deleting an element from a linked priority queue

The first node in the list will be deleted, and its data will be processed first.

Array Representation of Priority Queue

Priority queues can be also implemented using arrays. For each priority number, a separate circular queue is used. Each queue will have its own FRONT and REAR pointers.

Take a look at the two-dimensional representation of a priority queue given below.

Array Representation of Priority Queue
Array Representation of Priority Queue

Kth row in matrix maintains the queue of elements with priority number k. FRONT[K] and REAR[K] contain the FRONT and REAR elements of row K of the queue.

Inserting a new element in a priority queue using array

  • Find the smallest K such that FRONT[K] ≠ NULL.
  • Delete and process the FRONT element in row K of queue.

Deleting an element from a priority queue using array

  • Insert ITEM as the REAR element in row M of queue.
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments