Java Data Structures and Algorithms for Beginners

Priority Queue Data Structure

Definition and Concepts

A priority queue is an abstract data structure that operates similarly to a regular queue but assigns a priority to each element. Elements with higher priority are dequeued before those with lower priority, regardless of their order of insertion. You can visualize a priority queue as a hospital emergency room where patients with more severe conditions are treated first, even if they arrived later. The primary operations include enqueue, which adds an element with a specified priority, and dequeue, which removes and returns the element with the highest priority. Additional operations include peek, which views the highest-priority element without removing it, and isEmpty, which checks if the priority queue is empty. Priority queues are typically implemented using a heap (often a binary heap) to ensure efficient priority-based operations.

Why Use It?

A priority queue is useful when you need to process elements based on their priority rather than their arrival order. It ensures that the most critical or highest-priority elements are handled first, making it ideal for scheduling, resource allocation, and optimization problems. Priority queues are efficient because they use a heap structure, which provides logarithmic time complexity for most operations.

Where to Use? (Real-Life Examples)

• Task Scheduling in Operating Systems: Operating systems use priority queues to schedule processes based on their priority levels, ensuring critical tasks are executed first.
• Hospital Emergency Systems: Emergency rooms prioritize patients based on the severity of their condition, using a priority queue to manage treatment order.
• Dijkstra’s Algorithm: Priority queues are used in graph algorithms like Dijkstra’s to select the next node with the smallest distance.
• Huffman Coding: Priority queues are used to build optimal prefix codes for data compression by repeatedly selecting the two nodes with the smallest frequencies.

Explain Operations

• Enqueue: This operation adds an element with a specified priority to the priority queue. The element is inserted into the heap, and the heap property is restored by bubbling up. It has a time complexity of O(log n).
• Dequeue: This operation removes and returns the element with the highest priority (the root in a min-heap). The last element is moved to the root, and the heap property is restored by bubbling down. It has a time complexity of O(log n).
• Peek: This operation returns the highest-priority element (the root) without removing it. It has a time complexity of O(1).
• isEmpty: This operation checks whether the priority queue is empty. It has a time complexity of O(1).
• Size: This operation returns the number of elements in the priority queue. It has a time complexity of O(1).

Java Implementation

The following Java code implements a priority queue using a binary min-heap, where smaller values have higher priority.

public class PriorityQueue {
    private int[] heap; // Array to store the heap elements
    private int maxSize; // Maximum size of the priority queue
    private int size; // Current number of elements in the priority queue

    // Constructor to initialize the priority queue with a given size
    public PriorityQueue(int capacity) {
        maxSize = capacity;
        heap = new int[maxSize];
        size = 0; // Priority queue is initially empty
    }

    // Enqueue: Adds an element to the priority queue
    public void enqueue(int value) {
        if (size >= maxSize) { // Checks if the priority queue is full
            throw new IllegalStateException("The priority queue is full.");
        }
        heap[size] = value; // Adds the new element at the end
        bubbleUp(size); // Restores heap property by bubbling up
        size++; // Increments the size
    }

    // Dequeue: Removes and returns the highest-priority element
    public int dequeue() {
        if (isEmpty()) { // Checks if the priority queue is empty
            throw new IllegalStateException("The priority queue is empty.");
        }
        int result = heap[0]; // Stores the root (highest-priority element)
        heap[0] = heap[size - 1]; // Moves the last element to the root
        size--; // Decrements the size
        if (size > 0) { // Avoids bubbling down if the heap is empty
            bubbleDown(0); // Restores heap property by bubbling down
        }
        return result;
    }

    // Peek: Returns the highest-priority element without removing it
    public int peek() {
        if (isEmpty()) { // Checks if the priority queue is empty
            throw new IllegalStateException("The priority queue is empty.");
        }
        return heap[0]; // Returns the root element
    }

    // isEmpty: Checks if the priority queue is empty
    public boolean isEmpty() {
        return size == 0;
    }

    // Size: Returns the number of elements in the priority queue
    public int size() {
        return size;
    }

    // Helper method to bubble up an element to restore min-heap property
    private void bubbleUp(int index) {
        int parent = (index - 1) / 2; // Calculates parent index
        while (index > 0 && heap[index] < heap[parent]) { // Compares with parent
            swap(index, parent); // Swaps if child is smaller
            index = parent; // Updates index to parent
            parent = (index - 1) / 2; // Recalculates parent
        }
    }

    // Helper method to bubble down an element to restore min-heap property
    private void bubbleDown(int index) {
        int minIndex = index; // Tracks the smallest element
        while (true) {
            int leftChild = 2 * index + 1; // Left child index
            int rightChild = 2 * index + 2; // Right child index
            if (leftChild < size && heap[leftChild] < heap[minIndex]) {
                minIndex = leftChild; // Updates if left child is smaller
            }
            if (rightChild < size && heap[rightChild] < heap[minIndex]) {
                minIndex = rightChild; // Updates if right child is smaller
            }
            if (minIndex == index) break; // Stops if no smaller child found
            swap(index, minIndex); // Swaps with the smaller child
            index = minIndex; // Updates index to continue bubbling down
        }
    }

    // Helper method to swap two elements in the heap
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

How It Works

1. Initialization: The constructor initializes an array of size maxSize and sets size to 0, indicating an empty priority queue.
2. Enqueue Operation:
   • The method checks if the priority queue is full by comparing size to maxSize.
   • It adds the new element at the end of the heap (heap[size]), calls bubbleUp to restore the min-heap property by moving the element up if it’s smaller than its parent, and increments size.
   • If the queue is full, it throws an exception.
3. Dequeue Operation:
   • The method verifies that the priority queue is not empty using isEmpty().
   • It saves the root element (heap[0]), moves the last element (heap[size-1]) to the root, decrements size, and calls bubbleDown to restore the min-heap property by moving the root down if it’s larger than its children.
   • If the queue is empty, it throws an exception.
4. Peek Operation: The method returns the root element (heap[0]) without modifying the heap.
5. isEmpty Operation: The method returns true if size equals 0, indicating an empty priority queue, and false otherwise.
6. Size Operation: The method returns size, which represents the number of elements in the priority queue.
7. BubbleUp Helper: This method moves a newly added element up the heap by comparing it with its parent and swapping if it’s smaller, continuing until the heap property is restored.
8. BubbleDown Helper: This method moves the root element down by comparing it with its children, swapping with the smaller child if necessary, and continuing until the heap property is restored.
9. Swap Helper: This method exchanges two elements in the heap array.

Complexity Analysis Table

Key Differences / Notes

• Min-Heap vs. Max-Heap:
  • The implementation above uses a min-heap, where smaller values have higher priority. A max-heap can be implemented by reversing the comparison logic, where larger values have higher priority.
• Array-Based vs. Other Implementations:
  • The array-based heap implementation is memory-efficient and provides O(log n) for enqueue and dequeue operations.
  • Other implementations, like a binary search tree or linked list, are less common due to higher complexity or overhead.
• Thread Safety: The provided implementation is not thread-safe. For concurrent applications, use Java’s PriorityBlockingQueue or synchronize access.
• Java’s Built-in Priority Queue: Java provides java.util.PriorityQueue, which is a min-heap by default but can be customized for max-heap behavior using a comparator.

✅ Tip: Use a min-heap for scenarios where the smallest element has the highest priority (e.g., shortest path algorithms) and a max-heap for scenarios where the largest element has priority (e.g., task prioritization).

⚠ Warning: Ensure the priority queue’s capacity is sufficient for your use case to avoid overflow errors in the array-based implementation. For dynamic sizing, consider Java’s PriorityQueue class.

Exercises

1. Task Scheduler: Write a Java program that uses the priority queue implementation above to simulate a task scheduler. Enqueue tasks with priorities (represented as integers) and dequeue them in order of highest priority, printing each task as it’s processed.
2. Kth Largest Element: Create a program that uses a priority queue to find the kth largest element in an array of integers. Test it with at least three different arrays and k values.
3. Min-Heap to Max-Heap: Modify the priority queue implementation to support a max-heap (where larger values have higher priority). Test the modified version with enqueue and dequeue operations.
4. Dijkstra’s Algorithm: Implement Dijkstra’s algorithm for a weighted graph using the priority queue. Represent the graph as an adjacency list and compute the shortest paths from a source node.
5. Merge K Sorted Lists: Write a program that merges k sorted arrays into a single sorted array using a priority queue. Enqueue the first element of each array with its array index and value, and repeatedly dequeue and enqueue the next element from the same array.