Priority Queue (Data Structure)

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 list, array, 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

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. 

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.
 

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.

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.

• Advantages of Circular Queue
   
• Priority Queue Implementation
   
• Heap and Priority Queue
   
• Priority Queue Using Java
   
• Implementation of Priority Queue Using Linked Lists
   
• Priority Queue Using Array in C++
   
• Priority Queue of Pairs in C++ using Ordering
   
• Double-Ended Priority Queue
   

You may refer to our Guided Path on Code Studios for enhancing your skill set on DSA, Competitive Programming, System 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!