PriorityQueue.java

import java.util.Arrays;

public class PriorityQueue {
    private int capacity = 10;
    private int size = 0;
    private int[] items = new int[capacity];

    // Helper methods for parent, left child, and right child indices
    private int parentIndex(int index) {
        return (index - 1) / 2;
    }

    private int leftChildIndex(int index) {
        return 2 * index + 1;
    }

    private int rightChildIndex(int index) {
        return 2 * index + 2;
    }

    // Helper method to ensure capacity
    private void ensureCapacity() {
        if (size == capacity) {
            capacity *= 2;
            items = Arrays.copyOf(items, capacity);
        }
    }

    // Method to swap two elements in the array
    private void swap(int index1, int index2) {
        int temp = items[index1];
        items[index1] = items[index2];
        items[index2] = temp;
    }

    // Method to maintain heap property by bubbling up
    private void heapifyUp() {
        int index = size - 1;
        while (index > 0 && items[index] > items[parentIndex(index)]) {
            swap(index, parentIndex(index));
            index = parentIndex(index);
        }
    }

    // Method to maintain heap property by bubbling down
    private void heapifyDown() {
        int index = 0;
        while (leftChildIndex(index) < size) {
            int largerChildIndex = leftChildIndex(index);
            if (rightChildIndex(index) < size && items[rightChildIndex(index)] > items[largerChildIndex]) {
                largerChildIndex = rightChildIndex(index);
            }
            if (items[index] > items[largerChildIndex]) {
                break;
            } else {
                swap(index, largerChildIndex);
            }
            index = largerChildIndex;
        }
    }

    // Method to add an element to the priority queue
    public void add(int item) {
        ensureCapacity();
        items[size] = item;
        size++;
        heapifyUp();
    }

    // Method to remove and return the maximum element from the priority queue
    public int remove() {
        if (size == 0) {
            throw new IllegalStateException("Priority queue is empty");
        }
        int maxItem = items[0];
        items[0] = items[size - 1];
        size--;
        heapifyDown();
        return maxItem;
    }

    // Method to return the maximum element from the priority queue without removing it
    public int peek() {
        if (size == 0) {
            throw new IllegalStateException("Priority queue is empty");
        }
        return items[0];
    }

    // Method to check if the priority queue is empty
    public boolean isEmpty() {
        return size == 0;
    }

    // Method to return the size of the priority queue
    public int size() {
        return size;
    }

    // Method to print the elements of the priority queue
    public void print() {
        for (int i = 0; i < size; i++) {
            System.out.print(items[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        PriorityQueue pq = new PriorityQueue();
        pq.add(5);
        pq.add(10);
        pq.add(3);
        pq.add(7);
        pq.add(1);
        pq.add(8);

        System.out.println("Priority Queue elements:");
        pq.print();

        System.out.println("Removing maximum element: " + pq.remove());
        System.out.println("Priority Queue elements after removal:");
        pq.print();
    }
}