What is a priority queue, and how is it implemented using a heap data structure?

A priority queue is a data structure that stores a collection of elements, each with a priority, and allows elements with higher priorities to be dequeued or removed before elements with lower priorities. Priority queues are commonly used in algorithms such as Dijkstra’s shortest path algorithm and Huffman coding.

One way to implement a priority queue is using a heap data structure, which is a complete binary tree where each node has a priority value that is either greater than or equal to its children’s priority values (in a max heap) or less than or equal to its children’s priority values (in a min heap).

In a max heap implementation of a priority queue, the element with the highest priority (i.e., the largest priority value) is stored at the root of the heap, and elements are dequeued by removing the root and reorganizing the heap so that the next highest priority element becomes the new root.

Here is an example implementation of a max heap-based priority queue in Java:

public class PriorityQueue {
    private int[] heap;
    private int size;
    
    public PriorityQueue(int capacity) {
        heap = new int[capacity];
        size = 0;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == heap.length;
    }
    
    public void enqueue(int value) {
        if (isFull()) {
            throw new IllegalStateException("Priority queue is full.");
        }
        heap[size] = value;
        siftUp(size);
        size++;
    }
    
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Priority queue is empty.");
        }
        int result = heap[0];
        size--;
        heap[0] = heap[size];
        siftDown(0);
        return result;
    }
    
    private void siftUp(int index) {
        int parentIndex = (index - 1) / 2;
        if (index > 0 && heap[index] > heap[parentIndex]) {
            swap(index, parentIndex);
            siftUp(parentIndex);
        }
    }
    
    private void siftDown(int index) {
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        int maxIndex = index;
        if (leftChildIndex < size && heap[leftChildIndex] > heap[maxIndex]) {
            maxIndex = leftChildIndex;
        }
        if (rightChildIndex < size && heap[rightChildIndex] > heap[maxIndex]) {
            maxIndex = rightChildIndex;
        }
        if (index != maxIndex) {
            swap(index, maxIndex);
            siftDown(maxIndex);
        }
    }
    
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

In this implementation, the priority queue is represented using a max heap data structure stored in an integer array called heap. The size variable keeps track of the number of elements in the priority queue.

The enqueue method inserts a new element into the priority queue and ensures that the heap property is maintained by calling the siftUp method, which swaps the new element with its parent if it has a higher priority.

The dequeue method removes the element with the highest priority from the priority queue and ensures that the heap property is maintained by calling the siftDown method, which swaps the root element with its highest priority child until the heap property is restored.

The siftUp method compares the priority of the new element with its parent’s priority and swaps them if necessary to maintain the heap property.