A priority queue is an abstract data type similar to a regular queue or stack data structure, but where each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.

Understanding Heap:

A heap is a specialized tree-based data structure that satisfies the heap property. In a max heap, for any given node I, the value of I is greater than or equal to the values of its children. In a min heap, the value of I is less than or equal to the values of its children.


import java.util.PriorityQueue;
class PriorityQueueExample {
  public static void main(String[] args) {
    PriorityQueue pq = new PriorityQueue<>();
    pq.add(10);
    pq.add(20);
    pq.add(15);
    System.out.println(pq.poll()); // Outputs 10
  }
}

Example of Min-Heap:

In this example, the priority queue acts as a min-heap, where the smallest element is always at the front.


import java.util.PriorityQueue;
class MinHeapExample {
  public static void main(String[] args) {
    PriorityQueue minHeap = new PriorityQueue<>();
    minHeap.add(5);
    minHeap.add(1);
    minHeap.add(3);
    System.out.println(minHeap.poll()); // Outputs 1
  }
}

Example of Max-Heap:

Java's PriorityQueue does not support max-heap directly, but this can be implemented using a comparator.


import java.util.Collections;
import java.util.PriorityQueue;
class MaxHeapExample {
  public static void main(String[] args) {
    PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    maxHeap.add(5);
    maxHeap.add(1);
    maxHeap.add(3);
    System.out.println(maxHeap.poll()); // Outputs 5
  }
}

Custom Object in Priority Queue:

Priority queues can store custom objects if they implement Comparable or provide a Comparator.


import java.util.PriorityQueue;
class Task implements Comparable {
  String name;
  int priority;
  Task(String name, int priority) {
    this.name = name;
    this.priority = priority;
  }
  public int compareTo(Task t) {
    return this.priority - t.priority;
  }
}
class CustomObjectExample {
  public static void main(String[] args) {
    PriorityQueue taskQueue = new PriorityQueue<>();
    taskQueue.add(new Task("Task1", 2));
    taskQueue.add(new Task("Task2", 1));
    System.out.println(taskQueue.poll().name); // Outputs Task2
  }
}

Heap Sort Using Priority Queue:

Heap sort can be implemented using a priority queue by inserting all elements and then polling them in sorted order.


import java.util.PriorityQueue;
class HeapSortExample {
  public static void main(String[] args) {
    int[] arr = {3, 1, 4, 1, 5, 9};
    PriorityQueue pq = new PriorityQueue<>();
    for (int num : arr) {
      pq.add(num);
    }
    while (!pq.isEmpty()) {
      System.out.print(pq.poll() + " "); // Outputs 1 1 3 4 5 9
    }
  }
}

Using Priority Queue for Scheduling:

Priority queues are often used in scheduling algorithms where tasks need to be processed based on priority.


import java.util.PriorityQueue;
class SchedulingExample {
  public static void main(String[] args) {
    PriorityQueue scheduler = new PriorityQueue<>();
    scheduler.add(new Task("Low Priority", 3));
    scheduler.add(new Task("High Priority", 1));
    System.out.println(scheduler.poll().name); // Outputs High Priority
  }
}

Merging K Sorted Lists:

Priority queues can be used to efficiently merge k sorted lists by always extracting the smallest head element.


import java.util.PriorityQueue;
class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}
class MergeKListsExample {
  public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode list : lists) {
      if (list != null) {
        pq.add(list);
      }
    }
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    while (!pq.isEmpty()) {
      current.next = pq.poll();
      current = current.next;
      if (current.next != null) {
        pq.add(current.next);
      }
    }
    return dummy.next;
  }
}

Finding Kth Largest Element:

A priority queue can be used to find the kth largest element in an array by maintaining a min-heap of size k.


import java.util.PriorityQueue;
class KthLargestElementExample {
  public int findKthLargest(int[] nums, int k) {
    PriorityQueue minHeap = new PriorityQueue<>();
    for (int num : nums) {
      minHeap.add(num);
      if (minHeap.size() > k) {
        minHeap.poll();
      }
    }
    return minHeap.peek();
  }
}

Dijkstra's Algorithm:

Priority queues are crucial in Dijkstra's algorithm for finding the shortest path in a graph.


import java.util.*;
class DijkstraExample {
  static class Node implements Comparable {
    int vertex, weight;
    Node(int v, int w) {
      vertex = v;
      weight = w;
    }
    public int compareTo(Node n) {
      return this.weight - n.weight;
    }
  }
  public int[] dijkstra(int V, ArrayList> adj, int S) {
    PriorityQueue pq = new PriorityQueue<>();
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[S] = 0;
    pq.add(new Node(S, 0));
    while (!pq.isEmpty()) {
      Node node = pq.poll();
      for (Node neighbor : adj.get(node.vertex)) {
        if (dist[node.vertex] + neighbor.weight < dist[neighbor.vertex]) {
          dist[neighbor.vertex] = dist[node.vertex] + neighbor.weight;
          pq.add(new Node(neighbor.vertex, dist[neighbor.vertex]));
        }
      }
    }
    return dist;
  }
}