Priority Queue in Data Structure

What is Priority Queue?

A priority queue serves as a specialized data structure where elements are organized based on their priority values, ensuring that higher-priority items are processed before lower-priority ones. This organization enables efficient retrieval of the most critical elements.

Various implementations, such as arrays, linked lists, heaps, or binary search trees, offer different trade-offs in terms of efficiency and flexibility.

Priority queues find extensive applications in scenarios demanding real-time processing, where prompt handling of high-priority tasks is crucial. They also play a pivotal role in algorithmic optimizations, facilitating tasks like Dijkstra’s algorithm for shortest path finding and the A* search algorithm for efficient pathfinding in graphs.

Characteristics of a Priority Queue

A queue is called a Priority Queue when it has the following characteristics:

• Each item in the queue must have a priority associated with it.
• Higher or lower priority elements must be dequeued before lower or higher priority elements respectively depending on priority order taken by user that is if user consider lower number as higher priority or higher number as higher priority.
• If two elements in the queue have the same priority value then the first in first out rule is followed for these two elements alone i.e. the element that entered the priority queue first will be the first to be removed.

Operations of a Priority Queue

A Priority Queue supports the following operations:

Insertion in a Priority Queue

When adding a new element to a priority queue, it's initially placed in the next available slot from top to bottom and left to right. However, if the new element is not in its correct position according to the priority order, it's compared with its parent node. If the new element is out of order, it's swapped with its parent, and this process continues recursively until the element is correctly positioned relative to its parent and all other elements in the queue.

Deletion in a Priority Queue

In a max heap, the root node holds the maximum element, and it's the first to be removed when prioritized removal is required. This removal action leaves an empty slot at the root, which is subsequently filled by promoting the last inserted element to the root position. After insertion, the newly placed element is compared with its parent and possibly swapped to maintain the heap property, ensuring that the highest priority element remains at the root. This comparison and potential swapping process continue recursively down the heap until the entire structure adheres to the max heap invariant.

Peek in a Priority Queue

This operation facilitates retrieving the maximum element from a Max Heap or the minimum element from a Min Heap without removing the node from the priority queue.

Extract-Max/Min from the Priority Queue

The operation Extract-Max retrieves and removes the node with the maximum value from a Max Heap, while Extract-Min performs the same action for a Min Heap, returning the node with the minimum value.

Types of Priority Queue

There are two types of Priority Queues:

1. Ascending Order Priority Queue

In an ascending order priority queue, all the elements are compared with another and the rule: The smaller the element(number), the higher the priority is applied. Let us consider a priority queue having the following priorities: 4,2,6,1,8 The first step would be to arrange them in ascending order as follows: 1,2,4,6,8

In this priority queue, 1 is the smallest number and is hence the item with the highest priority. On the other hand, 8 is the largest number and is hence the item with the lowest priority.

2. Descending Order Priority Queue

In a descending order priority queue, all the elements are compared with another and the rule: The larger the element(number), the higher the priority. Let us consider a priority queue having the following priorities: 4,2,6,1,8 The first step would be to arrange them in descending order as follows: 8,6,4,2,1

In this priority queue, 8 is the largest number and is hence the item with the highest priority. On the other hand, 1 is the smallest number and is hence the item with the lowest priority.

Implementation of Priority Queue in Data Structures

A Priority Queue is implemented using one of the 4 Data Structures:

1. Implementation Using Linked List

In the linked list, the element having higher priority will be present at the head of the list. Then, based on priority, all the elements in the list are arranged in descending order based on priority.

Class Declaration:

To insert an element, the list is traversed until a suitable position is found for the element to be inserted in order to maintain the overall order of the linked list. Hence, the worst time complexity is O(n) as the worst case is when all elements of the list need to be traversed.

For example, let us consider the linked list:

Let us consider that we need to insert an element with priority 8. 8 has a priority lower than 5 so we traverse the linked list till we find a position where it is suitable. The linked list will then look like this:

For deletion, the highest priority element will be removed first from the priority queue and the highest priority element is at the head of the list and hence it will simply be removed.

peek() is used to retrieve the highest priority element without removing it and this is also present at the head of the list.

Since the highest priority element is present at the head of the list, it takes just O(1) time to remove it or to do the peek() operation.

2. Implementation Using Binary Heap

Binary Heaps are a preferred data structure for implementing priority queues due to their efficient performance compared to arrays or linked lists. The heap properties ensure that the entry with the largest key is always at the top, allowing for immediate removal. Although restoring the heap property after removal takes O(log n) time for the remaining keys, this time can be combined with the O(log n) time needed for inserting a new entry if required immediately. This efficiency is particularly advantageous for large values of n, as heaps are efficiently represented in contiguous storage and guarantee logarithmic time complexity for both insertions and deletions.

3. Implementation Using Array

There are two ways to go about implementation of priority queues using arrays. The first is to use an ordered array and the other is to use an unordered array. In an ordered array, all the elements are ordered according to priority.

To insert a new element, you must traverse the array and insert it in such a way that the ordering is maintained. The worst case is hence O(n). Since they are in order, both the delete and the peek operations take O(1) time.

In an unordered array, all the elements are not arranged according to priority. Hence to insert an element, it does not matter where you insert it and hence it takes O(1) time.

However, to do the delete and peek operation, you must traverse the array and hence, the worst-case time complexity is O(n) for both.

4. Implementation Using Binary Search Tree

To maintain items efficiently in sorted order, a binary search tree is utilised. The binary search tree becomes a priority queue if the sort order is based on priority.

The time complexity to locate the top priority element is constant.

An extra pointer is kept to store the highest priority element, which will be updated as the insertion and deletion operations are completed. We will update the additional pointer with the deletion action by identifying the inorder successor.

Priority Queue Implementations in Python, Java, C, and C++

Implementation in Python

Implementation in Java

Implementation in C

Implementation in C++

Output:

Applications of Priority Queue

• Djikstra’s Algorithm – To find the shortest path between nodes in a graph.
• Prim’s Algorithm – To find the Minimum Spanning Tree in a weighted undirected graph.
• Heap Sort – To sort the Heap Data Structure
• Huffman Coding – A Data Compression Algorithm
• It is used in Operating Systems for:
  1. Priority Scheduling – Where processes must be scheduled according to their priority.
  2. Load Balancing – Where network or application traffic must be balanced across multiple servers.
  3. Interrupt Handling – When a current process is interrupted, a handler is assigned to the same to rectify the situation immediately.
• A* Search Algorithm – A graph traversal and a path search algorithm

Advantages of Priority Queue

1. Priority queues offer fast access to the highest priority element, streamlining retrieval without exhaustive searching.
2. Dynamic ordering enables priority values to be updated, facilitating automatic reordering as priorities shift.
3. They support efficient algorithm implementation, enhancing performance in tasks like Dijkstra's shortest path and A* search.
4. Priority queues find application in real-time systems for their ability to swiftly retrieve high-priority elements, critical in time-sensitive environments.

Disadvantages of Priority Queue

1. Priority queues pose complexity challenges compared to simpler data structures like arrays or linked lists, potentially demanding more intricate implementation and upkeep.
2. They can consume significant memory due to the storage of priority values for each element, which may be problematic in resource-constrained environments.
3. Despite their versatility, priority queues may not always be the optimal choice, as alternative structures like heaps or binary search trees might offer better efficiency for specific operations.
4. Predictability may vary with priority queues, as element retrieval depends on priority values rather than strict FIFO or LIFO order, leading to less deterministic outcomes in certain scenarios.

See More:

• Priority Queue in C++
• Java Priority Queue
• Priority Queue in Python