## 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.

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.

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.

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