What is a Priority Queue?

A Priority Queue is an abstract data type that operates similarly to a regular queue, but with an additional twist: elements are served based not on their order in the queue, but rather on their priority. In other words, an element with a higher priority is dequeued before an element with a lower priority, regardless of their order in the queue.

For example, consider a hospital's emergency room where patients are treated based on the severity of their conditions rather than the order in which they arrive. Critical cases (high priority) are treated before those who are stable (low priority).

Implementing a Priority Queue in Java:

Java provides a built-in class PriorityQueue that can be used to implement a priority queue:

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // Create a priority queue
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // Adding elements
        pq.add(5);
        pq.add(1);
        pq.add(3);
        pq.add(2);

        // Polling elements (should return the smallest, 1)
        System.out.println("Polled element: " + pq.poll());
        System.out.println("Next element: " + pq.peek()); // Should return 2

        // Printing remaining elements
        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

In this example, we added several integers to the priority queue, and when we polled the elements, it returned them in ascending order.

Understanding Heaps

Heaps are a specific type of binary tree that satisfy the heap property. There are two types of heaps: min-heaps and max-heaps.

• In a min-heap, for any given node i, the value of i is less than or equal to the values of its children. Thus, the smallest element can always be found at the root.
• Conversely, in a max-heap, the value of i is greater than or equal to the values of its children, with the largest element at the root.

Visual Representation:

Here's a simple representation of a min-heap:

       1
      / \
     3   2
    / \
   6   5

How Priority Queue Uses Heaps

Internally, the PriorityQueue class in Java is implemented using a heap data structure. When elements are added to the priority queue, they are organized in a way that the highest priority (or least value in a min-heap) can be accessed in constant time.

Creating a Min-Heap in Java:

You can also implement a heap from scratch. Here’s an example of a simple min-heap structure:

public class MinHeap {
    private int[] heap;
    private int size;

    public MinHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    public void insert(int value) {
        if (size == heap.length) {
            throw new IllegalStateException("Heap is full");
        }
        heap[size] = value;
        size++;
        heapifyUp();
    }

    private void heapifyUp() {
        int index = size - 1;
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap[index] >= heap[parentIndex]) break;
            swap(index, parentIndex);
            index = parentIndex;
        }
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public int remove() {
        if (size == 0) throw new IllegalStateException("Heap is empty");
        int root = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown();
        return root;
    }

    private void heapifyDown() {
        int index = 0;
        while (index < size) {
            int leftChild = index * 2 + 1;
            int rightChild = index * 2 + 2;
            int smallest = index;

            if (leftChild < size && heap[leftChild] < heap[smallest]) {
                smallest = leftChild;
            }
            if (rightChild < size && heap[rightChild] < heap[smallest]) {
                smallest = rightChild;
            }
            if (smallest == index) break;
            swap(index, smallest);
            index = smallest;
        }
    }
}

// Usage
 public class Main {
     public static void main(String[] args) {
         MinHeap minHeap = new MinHeap(10);
         minHeap.insert(3);
         minHeap.insert(1);
         minHeap.insert(4);
         minHeap.insert(2);
         System.out.println("Removed element: " + minHeap.remove()); // Should print 1
     }
 }

In this implementation, we maintain the heap structure by adding elements and ensuring the min-heap property is maintained both when inserting and removing an element.

The ability to prioritize elements effectively and utilize the structure of heaps to manage large datasets is integral in several applications, including task scheduling, graph algorithms like Dijkstra’s, and more.

Understanding how these structures work will not only enhance your coding interviews and practical applications but also empower you to tackle complex problems with confidence!