What is a Priority Queue?

A priority queue is a type of Queue in the data structure and algorithms. It is an abstract data type and a special kind of queue. It is somehow similar to a normal queue the only difference is in the priority queue all the elements of the queue are arranged according to their priority.

In the priority queue, all elements are associated with a defined priority and all the elements are arranged in their priority order.

You can also explore: Queue Data Structure: Types, Implementation, Applications

In this article, we are going to discuss what exactly the priority queue is, the properties of the priority queue, types of the priority queue, how any element’s priority is assigned, operations performed on the priority queue like insertion, deletion, finding the minimum or maximum element of the queue, the difference between a simple queue and priority queue, complexity of priority queue, and applications of the priority queue.

What is a Priority Queue?

The priority queue is a special queue and an abstract data type, this is a type of queue in which each element is associated with a priority and the elements are arranged in the queue as per their priority. 

Also explore: Data Structures and Algorithms Online Courses & Certifications

The element with the higher priority will be served first, and if two elements share the same priority then they will be served on the basis of their occurrence, which means the element who entered the queue first will have more priority over others. 

Properties of priority queue:

A priority queue is an extended version of the normal queue with the only difference being that its elements have a priority value associated with them. So the priority queue has a few properties, which are as follows:

1. Every element of the queue has a priority assigned to it.
2. The element with the highest priority is served first or will be dequeued before the element having low priority.
3. Two elements with the same priority appear, then they will be served on the basis of their occurrence. The one who occurred first will be dequeued first.

You must explore: Deque – All That You Need To Know

You can also explore: Difference between Stack and queue

Assigning Priority value to Elements

In the priority queue, generally, the value of an element is assigned as the priority of that element. The element with the largest value will be assigned the largest priority, and similarly, the smallest value will have the least priority. Also, the lowest value can have the highest priority and the highest value is having the lowest priority.

Also Read: Top Data Structure Interview Questions [DS and Algorthims]

Types of Priority Queue

Priority Queue is of two types:

1. Ascending order Priority
2. Descending order Priority

Ascending order Priority:

In Ascending order priority queue, the element with least value has the highest priority. 

For example, 

In the above queue, elements are arranged as per their priority in ascending order. So, if we need to deque an element from the above queue 5 will be first element to be dequed. 

Descending order Priority:

In Descending order priority queue, the element with the highest value has the highest priority. 

For example, 

In the above queue, elements are arranged as per their priority in descending order. So, if we need to deque an element from the above queue 25 will be the first element to be dequeued. 

You can also explore: Difference between Stack and queue

Operation on Priority Queue

The following operations are performed on a priority queue:

• Insertion
• Deletion
• Peek

Also Read: Top Data Structure Interview Questions [DS and Algorthims]

Insertion:

Insertion operation is used to insert a new element into the queue. Whenever a new element is inserted, 

• The new element is moved to an empty slot top to bottom and left to right. 
• If the inserted element is not in the correct position. It will be compared with the parent element. 
• And if the element is not in the correct order, then elements are swapped until the inserted element gets to the correct position. 

Algorithm:

if (the queue is empty)

Create a node

else                                             //when node is already present

Insert the new node at the end of the queue (last node from left to right)

heapify the array

Deletion:

Deletion operation is used to remove any element from the queue, For deleting any element, 

• Choose the element which needs to be deleted.
• Swap it with the last element.
• Remove the last element
• Heapify the array.

Algorithm:

if (node== leaf node)

delete  node

else                                              //when node is not leaf node

Swap node with leaf node

Delete the leaf node

heapify the array

Peek:

Peeking an element means returning either maximum or minimum element of the array. Peek operation is used to find out maximum or minimum element of the array. It is just returning the value of highest or lowest element without deleting that node. 

Extract:

Extract operation is used to remove the peeked value. In simple, words the highest or lowest value of the array is identified with the help of peek operation and it can be removed using extract operation. 

You must also explore: 8 Most Important Data Structures Every Programmer Must Know

Implementation of Priority Queue

Priority queue can be implemented using a array, linked list, binary search tree or heap data structure. Among all these data structure heap is the most efficient implementation of priority queue. 

Using Array:

The basic implementation using array is:

struct node

{

   int node:

   int priority:

}

Operations in array:

• enqueue(): It is used to insert new element into the priority queue.
• dequeue(): It removes an element with the highest priority from the priority queue.
• peek(): It is used to determine the highest priority element in the queue without removing it.

Using Linked list:

For implementing priority queue using linked list, first sort all the elements in the ascending order and keep them as per their priority means elements with greater value will have higher priority and elements with smaller number will have lower priority or vice versa. 

Operations in Linked list:

• push(): It is used to insert new element into the priority queue.
• pop():  It removes an element with the highest priority from the priority queue.
• peek(): It is used to determine the highest priority element in the queue without removing it.

Using Heap:

Heap are the preferred data structure for the implementation of priority queue as compared to array and linked list because heaps are most efficient and provide better performance when compared with other data structure.

Operations in Heap:

• insert:  It is used to insert new element into the priority queue.
• remove: This function removes the element pointed by the iterator.
• getMax(): This function returns  the maximum priority element.
• extractMax(): This function extracts the maximum priority element .
• changePriority: Changes the priority of an element.

Using Binary Search Tree

A binary search tree can be used to implement priority queue. Like AVL tree, Red-Black tree are the binary trees and can be used to implement the priority queue and all the operations like insert, delete, peek can be performed using these BSTs. 

You can also explore: All About Balanced Binary Tree

Difference between Simple queue and priority queue

There is only one main difference between a simple queue and a priority queue, which is already discussed each element of the priority queue is associated with a priority and that priority defines which element will be dequeued first. 

A simple queue is based on FIFO (First In First Out manner) whereas a priority queue is based on the priority of each element. 

Complexity:

The time complexity of different operations when implemented using different data structures are as follows:

Data Structure	Insert	Delete	Peek
Linked List	O (n)	O (1)	O (1)
Binary Heap	O (log n)	O (log n)	O (1)
Binary Search Tree	O (log n)	O (log n)	O (1)

Applications of Priority Queue

• Shortest path graph algorithm like Prim’s Minimum Spanning tree, Dijkstra’s shortest path algorithm. 
• Data compression in Huffman code.
• CPU scheduling.
• Finding largest/ smallest element. 
• Impelmeting stack.

Author: Kanika Joshi