Priority Queue Data Structure

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.

Characteristics of a Priority queue:

• Each element in a priority queue is assigned a priority.
• An element with high priority is dequeued before one with low priority.
• If two or more elements have the same priority, they are processed based on their order of insertion in the queue.

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.

Given a simple example of Priority Queue in Java.

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 + " ");
    }
  }
}

Queue is full.
Element removed from the Priority Queue: 15
Element at front: 25
--------------------
index : 4 3 2  1  0
--------------------
Queue:  25 35 45 55

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.