Priority Queues

A queue which serves elements based on priority, irrespective of their insertion order.

Real Life Example

• In Hospital 🏥
• Patient A: Fever
• Patient B: Accident
• Patient C: Headache

Here, Tasks with higher priority should be treated first.

• Normal Queue (FIFO) A -> B -> C
• Priority Queue (Highest Priority) B -> C -> A
• Higher the Priority faster will be treated.

Use Cases:

• CPU Scheduling
• Cache System
• Real Time Systems
• Dijkstra’s Algorithm

Implementation of Priority Queue

1. Sorting

Implementation

• Whenever you add elements, ensure that the highest priority element is at the front.
• When you add elements, make sure you sort them in descending order.

            
            priorityQueue.push(val);
            priorityQueue.sort();   // In descending order
            
        

Time Complexity

• To add an element O(nlogn)

  Sorting is one way to implement a priority queue, but it has very high time complexity.

  So, Sorting is not efficent way to handling Priority Queue.

2. Heap

Note

• Heap and Priority Queue is not the same thing.
• Heap is Data structure.
• Priority Queue is abstract data type.
• We use Heap to implement Priority Queue.

A Max Heap always ensures that the maximum value is at the top.

Time Complexity: O(logn)

This process is efficient for insertions and deletions.

Priority Queue’s are Two Types:

• Max Priority Queue: Where the element with the highest value has the highest priority and is served before all other elements.
• Min Priority Queue: Where the element with the lowest value has the highest priority and is served before all other elements.

Both are very similar to maxHeap and minHeap.

Implementation of Priority Queue

Java:

      import java.util.PriorityQueue;
      import java.util.Collections;   // For reverseOrder()
        
      public class PriorityQueueExample {
        
      public static void main(String[] args){
        // Default min-heap (natural ordering)
        
        PriorityQueue minHeap = new PriorityQueue<>();
        
        minHeap.add(5);
        
        minHeap.add(1);
        
        minHeap.add(8);
        
        System.out.println("Min-Heap Head: " + minHeap.peek());
        System.out.println("Removed from Min-Heap: " + minHeap.poll());  
        
        // Max-heap using a custom Comparator
        PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        
        maxHeap.add(5);
        
        maxHeap.add(1);
        
        maxHeap.add(8);
        
        System.out.println("Max-Heap Head: " + maxHeap.peek());
        System.out.println("Removed from Max-Heap: " + maxHeap.poll());
    }
}

Java has an in-built PriorityQueue.

Python:

Python provides two main ways to implement priority queues:

heapq module: This module provides an implementation of the heap queue algorithm, which is a min-heap. This means the smallest element (highest priority in a typical priority queue implementation, where lower values indicate higher priority) is always at the root of the heap.

            import heapq
            #Create an empty heap (List)
            priority_queue=[]

            #Add elements as (priority, value) tuples
            heapq.heappush(priority_queue, (2, "Task B"))
            heapq.heappush(priority_queue, (1, "Task A"))
            heapq.heappush(priority_queue, (3, "Task C"))

            #Retrieve and remove elements (Lowest priority value first)
            while priority_queue:
                priority, value = heapq.heappop(priority_queue)
                print(f"Processing task: {value} (Priority: {priority})")
        

queue.PriorityQueue class: This class from the queue module provides a thread-safe implementation of a priority queue, suitable for concurrent applications.

            from queue import PriorityQueue

            # Create a PriorityQueue object
            priority_queue = PriorityQueue()

            # Add elements as (priority, value) tuples
            priority_queue.put((2, "Task B"))
            priority_queue.put((1, "Task A"))
            priority_queue.put((3, "Task C"))

            # Retrieve and remove elements (lowest priority value first)
            while not priority_queue.empty():
                priority, value = priority_queue.get()
                print(f"Processing task: {value} (Priority: {priority})")
        

C++:

            #include <iostream>
            #include <queue> // Required for priority_queue

            int main() {
                std::priority_queue pq; // Creates a max-heap (default)

                pq.push(10);
                pq.push(30);
                pq.push(28);

                std::cout << "Top element: " << pq.top() << std::endl; // Output: 30

                pq.pop(); // Removes 30

                std::cout << "New top element: " << pq.top() << std::endl; // Output: 28

                return 0;
            }
        

JavaScript:

In Javascript does not have a built in Priority Queue / Heap.

You have to write your own implementation.