Untitled

package Day3;

import java.util.Arrays;

class Main {
    private int[] heap;
    private int size;
    private int capacity;

    public Main(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        heap = new int[capacity + 1]; // 1-based index
        heap[0] = Integer.MIN_VALUE; // Dummy value
    }

    private int parent(int i) {
        return i / 2;
    }

    private int leftChild(int i) {
        return 2 * i;
    }

    private int rightChild(int i) {
        return 2 * i + 1;
    }

    // Insert a new element into the heap
    public void insert(int value) {
        if (size >= capacity) {
            System.out.println("Heap is full!");
            return;
        }
        size++;
        heap[size] = value;
        heapifyUp(size);
    }

    // Heapify-Up to maintain Min-Heap property
    private void heapifyUp(int i) {
        while (i > 1 && heap[parent(i)] > heap[i]) {
            swap(i, parent(i));
            i = parent(i);
        }
    }

    // Get the minimum element (root)
    public int peek() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty!");
        }
        return heap[1];
    }

    // Remove and return the minimum element
    public int removeMin() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty!");
        }
        int min = heap[1];
        heap[1] = heap[size];//fist element replaced by last
        size--;
        heapifyDown(1);
        return min;
    }

    // Heapify-Down to maintain Min-Heap property
    private void heapifyDown(int i) {
        int smallest = i;
        int left = leftChild(i);
        int right = rightChild(i);

        if (left <= size && heap[left] < heap[smallest]) {
            smallest = left;
        }
        if (right <= size && heap[right] < heap[smallest]) {
            smallest = right;
        }
        if (smallest != i) {
            swap(i, smallest);
            heapifyDown(smallest);
        }
    }

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

    // Print the heap
    public void printHeap() {
        System.out.println("Heap: " + Arrays.toString(Arrays.copyOfRange(heap, 1, size + 1)));
    }

    public static void main(String[] args) {
        MinHeap pq = new MinHeap(10);
        
        // Insert elements
        pq.insert(30);
        pq.insert(20);
        pq.insert(10);
        pq.insert(40);
        pq.insert(50);
        pq.insert(5);
        
        pq.printHeap();

        // Peek min element
        System.out.println("Min element (peek): " + pq.peek());

        // Remove min element
        System.out.println("Removed min: " + pq.removeMin());
        pq.printHeap();

        System.out.println("Removed min: " + pq.removeMin());
        pq.printHeap();
    }
}