Priority Queue Data Structure

Last Updated: 18 January, 2025 🕓 6 Mins Read

Priority queues are a powerful data structure in computer science that provide efficient management of prioritized elements. They are widely used in many real-world applications and algorithms where prioritization is crucial for performance and correctness.

In this tutorial, we are going to explore what a priority queue is in data structure, types, basic operations, implementations, use cases in various real-world scenarios, advantages, and disadvantages.

What is a Priority Queue in Data Structure?

A priority queue is one particular kind of queue where each element of a queue is associated with a priority, and elements are processed according to their priority, which means higher-priority elements are processed first.

In a priority queue, elements are processed (dequeued) according to their priority rather than their order of insertion (FIFO). Higher priority elements are dequeued first, followed by lower priority elements.

For instance, priority queues are essential in scheduling tasks in operating systems, where processes with higher importance must be executed before those with lesser priority. Additionally, they play a vital role in graph algorithms, such as Dijkstra's and Prim's, where maintaining the order of exploration based on edge weights or distances is fundamental.

Assigning priority in a priority queue

In most cases, the element's value is taken into consideration for assigning the priority. As an illustration,

The highest priority element is the one with the highest value. In some situations, on the other hand, we can assume the element with the lowest value as the highest priority element. Setting priorities based on our requirements is also possible in the Priority Queue.

Priority Queue Implementation

We can implement a priority queue using an array, a linked list, a heap data structure, or a binary search tree. Heap data structures are more preferred as compared to other data structures because heap data structures provide an efficient way to implement priority queues.

  
  public class PriorityQueue {
    
    final int MAX;
    int[] intArray;
    int count;
  
    // Constructor
    public PriorityQueue(int size) {
      MAX = size;
      intArray = new int[MAX];
      count = 0;
    }
  
    // Method to insert an element into the PriorityQueue
    void insert(int data) {
      int i = 0;
  
      if (!isFull()) {
        // if queue is empty, insert the data
        if (count == 0) {
          intArray[count++] = data;
        } else {
          // start from the right end of the queue
          for (i = count - 1; i >= 0; i--) {
            // if data is larger, shift existing item to right end
            if (data > intArray[i]) {
              intArray[i + 1] = intArray[i];
            } else {
              break;
            }
          }
          // insert the data
          intArray[i + 1] = data;
          count++;
        }
      }
    }
  
    // Method to delete an element from the PriorityQueue
    public int remove() {
      return intArray[--count];
    }
  
    // Method to peek an element from the PriorityQueue
    public int peek() {
      return intArray[count - 1];
    }
  
    // Method to check Priority Queue is empty
    boolean isEmpty() {
      return count == 0;
    }
  
    // Method to check PriorityQueue is full
    boolean isFull() {
      return count == MAX;
    }
  
    // Method to return the size of the Priority Queue
    int size() {
      return count;
    }
  
    public static void main(String[] args) {
      // Create a Priority Queue
      PriorityQueue queue = new PriorityQueue(5);
  
      // Inserting an elements into the queue
      queue.insert(25);
      queue.insert(55);
      queue.insert(45);
      queue.insert(35);
      queue.insert(15);
  
      // Checking queue is full
      if (queue.isFull()) {
        System.out.println("Queue is full.");
      }
  
      // Remove an element from the queue
      int value = queue.remove();
      System.out.println("Element removed from the Priority Queue: " + value);
  
      System.out.println("Element at front: " + queue.peek());
      System.out.println("--------------------");
      System.out.println("index : 4 3 2  1  0");
      System.out.println("--------------------");
      System.out.print("Queue:  ");
  
      while (!queue.isEmpty()) {
        int n = queue.remove();
        System.out.print(n + " ");
      }
    }
  }

Applications of Priority Queue

Task Scheduling: A priority queue is used for tasks or jobs scheduling that means highter priority jobs or tasks execute first before the lower priority task.

Event-driven Simulation: Priority queues are used to manage events in a simulation, processing them in the order of their scheduled times.

Prim's Algorithm: This algorithm uses a priority queue to find the minimum spanning tree in a weighted, undirected graph.

Dijkstra's Algorithm: This algorithm uses a priority queue to find the shortest path between nodes in a graph.

E-commerce Platforms: Order fulfillment can be prioritized based on factors like delivery speed, order value, or customer status.

Multimedia Applications: Priority queues can manage audio and video streams, ensuring smooth playback and prioritizing important data.

Cybersecurity: Priority queues can manage threat alerts, prioritizing high-risk areas for scanning and response.

Data Analytics: Priority queues can structure data processing and reporting tasks, ensuring that important insights are prioritized.