Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Priority Queue?
3.
Applications of Priority Queue
4.
Characteristics of a Priority Queue
5.
Types of Priority Queues
5.1.
Ascending Order Priority Queue
5.2.
Descending Order Priority Queue
6.
Implementation of Priority Queues
7.
What is Heap?
7.1.
Max Heap
7.2.
Min Heap
8.
 
9.
Program to create the priority queue using the binary max heap
10.
Normal Queue vs Priority Queue
11.
Frequently Asked Questions
11.1.
1. What are the advantages and application of priority queue?
11.2.
2. What are the applications of priority queue?
11.3.
3. What is the examples of priority queue in data structure?
12.
Conclusion
Last Updated: Mar 27, 2024
Easy

Priority Queue (Data Structure)

Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

Hello Ninja! When we learn a new concept, we always wonder, "What is the use of this?" You must also have the same question about the priority queues. Do not worry; we will answer this question in this write-up. In this article, we will discuss the applications of priority queue.

application of priority queue

Let us start by recalling what priority queues are.

Also Read, Prefix Sum Array

What is Priority Queue?

Priority queues are similar to queues. The difference is that the elements do not come out in FIFO (First In, First Out) order. They come out based on their “priority.”

A priority is a value that marks the “importance” of a queue element. In a priority queue, the order of entry is not of much concern; the order of exit is. Each component of the priority queue is dequeued based on its priority. The priority can be of two types, depending on the situation.

Type 1: Lower value, higher priority

priority queue

Type 2: Higher value, higher priority.

priority queue
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Applications of Priority Queue

The following are some applications of the priority queues.

  • In Dijkstra’s algorithm, stores the graph in an adjacency list to use a priority queue.
     
  • In Prim’s Algorithm, uses a priority queue to store the keys of nodes.
     
  • In Artificial Intelligence, uses a priority queue to implement the A* search algorithm.
     
  • In Data compression, it uses a priority queue in Huffman Encoding to implement the min-heap.
     
  • In Operating Systems, use priority queues in the load-balancing algorithms.
     
  • In bandwidth management, Priority queues are used to prioritize important data packets.

 

  1. In Dijkstra’s algorithm
    We all know that if we want to find the minimum cost path from a source to a destination vertex, we use Dijkstra’s Algorithm. In the efficient approach of Dijkstra’s Algorithm, we store the graph in an adjacency list. We then use a priority queue to extract the minimum path. To learn more about this approach, go to Dijkstra's Algorithm.
     
  2. In Prim’s Algorithm 
    In the case of Prim’s Algorithm, we use a priority queue to store the keys of nodes. Then we extract minimum key nodes at every step.
     
  3. In Artificial Intelligence
    We use a priority queue to implement the A* search algorithm. The A* search algorithm first attempts the most promising routes to discover the shortest path between two vertices in a weighted graph. This type of queue ( also known as the fringe in the A* algorithm) keeps track of the unexplored routes. The one with the shortest lower bound on the total path length receives the most priority.
     
  4. In data compression 
    We use a priority queue in Huffman Encoding to implement the min-heap. Huffman Encoding is one of the famous data compression techniques used in compression formats like PKZIP and GZIP. 
     
  5. In Operating Systems
    We use priority queues in the load balancing algorithms. It maintains the flow of operations. Good load-balancing algorithms ensure a smoother flow. They optimize the response time in various computations. Interrupt handling also uses priority queues. The interrupts that have more priority are handled first.
     
  6. In bandwidth management
    Priority queues are used to prioritize essential data packets. The network can ensure that such packets reach their destination as soon as feasible.

Characteristics of a Priority Queue

The following are some characteristics of a priority queue:-

  • Elements are stored based on their associated priority values.
     
  • Highest and lowest priority elements can be accessed in constant time, irrespective of the number of elements present in the queue.
     
  • After every insertion or deletion, depending on the underlying Data structure, the queue is reorganized to maintain the order.
     
  • Only the highest priority element can be removed from a priority queue. You should use multisets to support removal of intermediary elements.
     
  • It can be implemented with binary search tree, binary heap, linked list or array, they all have different advantages and disadvantages.
     

In the next section you will learn about the different types of priority queues.

Types of Priority Queues

Priority queues are of two types, based on the priority given to the elements depending on their numerical values:-

Ascending Order Priority Queue

In this types of priority queue, numbers with smaller values are given higher priorities, i.e. the smallest element is at front of the queue.

Descending Order Priority Queue

In this types of priority queue, numbers with larger values are given higher priorities, i.e. the largest element is at front of the queue.

In the next section, you will look at the comparison between different implementations of priority queues.

Implementation of Priority Queues

You can implement priority queues in many ways. Implementation using binary search tree, linked listarray, and binary heap tree are most common. Out of these, the most efficient way to implement priority queues is using the heap data structure. 

The following image shows the worst-case time complexities of various ways to implement the priority queues.

Analysis of complexities using different implementations

Operation Using Unsorted Arrays Using Unsorted Linked List Using BST Using Heap
Enqueue O(1) O(1) O(logN) O(logN)
Dequeue O(N) O(N) O(logN) O(logN)

 

 

 

 

Without any further ado, let’s head to the applications of Priority Queue.

What is Heap?

A heap is a specialized tree data structure which is commonly used for implementing priority queues. The nodes are stored in a hierarchical order based on their values. It is usually implemented using an array, and the parent child relationships are maintained by their indices.

There are two types of heaps:

Max Heap

In a max heap, the value of each parent node is greater than or equal to the values of its children. This makes sure that the maximum value is at the root.

Min Heap

In a min heap, the value of each parent node is less than or equal to the values of its children. This makes sure that the minimum value is at the root.

In the next section, you will learn about some applications of priority queues.


 

Now a question arises, how are priority queues different from normal queues? Let’s find out.

Must Read Lower Bound in C++

Program to create the priority queue using the binary max heap

The following code in C++ uses the array implementation of binary max heap to implement the priority queue class:-

#include <iostream>
#include <vector>
class PQ {
private:
   std::vector<int> heap;
   void heapifyUp(int index) {
       if (index == 0)
           return;
       int parentIndex = (index - 1) / 2;
       if (heap[index] > heap[parentIndex]) {
           std::swap(heap[index], heap[parentIndex]);
           heapifyUp(parentIndex);
       }
   }
   void heapifyDown(int index) {
       int leftChildIndex = (2 * index) + 1;
       int rightChildIndex = (2 * index) + 2;
       int largest = index;
       if (leftChildIndex < heap.size() && heap[leftChildIndex] > heap[largest]) {
           largest = leftChildIndex;
       }
       if (rightChildIndex < heap.size() && heap[rightChildIndex] > heap[largest]) {
           largest = rightChildIndex;
       }
       if (largest != index) {
           std::swap(heap[index], heap[largest]);
           heapifyDown(largest);
       }
   }
public:
   void insert(int value) {
       heap.push_back(value);
       heapifyUp(heap.size() - 1);
   }
   int getMax() {
       if (heap.empty()) {
           std::cerr << "Heap is empty!" << std::endl;
           return -1; // Return some default value
       }
       return heap[0];
   }
   int deleteMax() {
       if (heap.empty()) {
           return -1; // Return some default value
       }
       int max = heap[0];
       std::swap(heap[0], heap[heap.size() - 1]);
       heap.pop_back();
       heapifyDown(0);
       return max;
   }
   bool isEmpty() {
       return heap.empty();
   }
};
int main() {
   PQ pq;
   pq.insert(30);
   pq.insert(10);
   pq.insert(50);
   pq.insert(20);
   std::cout << "Max element: " << pq.getMax() << std::endl;
   pq.deleteMax();
   std::cout << "Max element after deletion: " << pq.getMax() << std::endl;
   return 0;
}

 

Output

Max element: 50
Max element after deletion: 30

 

You should use the priority_queue data structure from the C++ standard template library, instead of implementing it from scratch.

Also read - Data Structure MCQ

Normal Queue vs Priority Queue

Imagine a scenario where ten people need to exit a room. The people are numbered according to their time of entry as P1, P2, P3 …. P5. That means that P1 entered first and P5 entered last. 

normal queue vs priority queue

If it were a normal queue exit, P1 would have exited first, then P2, P3, and so on. Look at the image that follows to visualize it.
 

normal queue vs priority queue

But now, there is a catch. Everyone in the room has different “statuses” or “priorities.” For example, P1 has priority 3, and P5 has priority 1. That means that P5 is of higher importance than P1. In this case, P5 will exit the room first (provided the priorities are in increasing order and lower values have more preference). The following image can help you visualize it better.

normal queue vs priority queue

If you have any doubts, head to our CN Library and read about Priority Queue.

Let us now address some frequently asked questions.

Read about Application of Queue in Data Structure here.

Frequently Asked Questions

1. What are the advantages and application of priority queue?

A major advantage of a priority queue is that it allows you to insert and remove data efficiently into an ordered collection of elements. It is commonly used in graph algorithms such as Dijkstra's and Prim's algorithm, it is also used for resource allocation and process scheduling in operating systems.

2. What are the applications of priority queue?

Priority queues have numerous applications, including task scheduling, shortest path algorithms, event-driven simulations, Huffman coding, and heap sort. They are also used in network routing protocols, and in various computer science and engineering fields that require sorting and searching of elements based on their priority.

3. What is the examples of priority queue in data structure?

Examples of priority queues in data structures include binary heaps, Fibonacci heaps, and binomial heaps. Other data structures, like balanced binary search trees and sorted arrays can also be used to implement priority queues, but they have different time complexities for various operations.

Conclusion

In a nutshell, we discussed the various applications of priority queue. We first discussed a summary of priority queues. Then we summed up our discussion with the different applications of priority queues. At last, we addressed some FAQs.

You can refer to these articles to learn more about the priority queues.

You may refer to our Guided Path on Code Studios for enhancing your skill set on DSACompetitive ProgrammingSystem Design, etc. Check out essential interview questions, and practice our available mock tests. Look at the interview bundle for interview preparations and so much more!

Happy Learning, Ninjas!

Live masterclass