Program to Implement Min Heap

// Java Program to Implement Min Binary Heap
import java.util.Arrays;

public class BinaryHeap {
  
     // Array representation of the heap
    private int[] heap;   
  
      // Number of elements currently in the heap
    private int size;     
  
      // Maximum number of elements the heap can hold
    private int capacity; 

    // Constructor to initialize the heap with a given capacity
    public BinaryHeap(int capacity) {
        this.capacity = capacity;
        this.heap = new int[capacity];
        this.size = 0;
    }

    // Method to get the index of the
      // parent of a given node
    private int parent(int i) {
        return (i - 1) / 2;
    }

    // Method to get the index of the
      // left child of a given node
    private int leftChild(int i) {
        return 2 * i + 1;
    }

    // Method to get the index of the
      // right child of a given node
    private int rightChild(int i) {
        return 2 * i + 2;
    }

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

    // Method to resize the heap array when capacity is reached
    private void resize() {
        capacity *= 2;
        heap = Arrays.copyOf(heap, capacity);
    }

    // Method to insert a new value into the heap
    public void insert(int value) {
        if (size >= capacity) {
              // Resize the heap if capacity is reached
            resize(); 
        }
      
          // Place the new value at the end of the heap
        heap[size] = value; 
      
          // Index of the newly added element
        int current = size; 
      
          // Increase the size of the heap
        size++;             

        // Restore the heap property by "heapifying up"
        while (current > 0 && heap[current] < heap[parent(current)]) {
              // Swap with the parent if smaller
            swap(current, parent(current)); 
          
              // Move up to the parent's position
            current = parent(current);      
        }
    }

    // Method to restore the heap property by
       // "heapifying down" from a given index
    private void heapifyDown(int i) {
           // Assume the current index is the smallest
        int smallest = i;
      
          // Get the left child index
        int left = leftChild(i);    
      
          // Get the right child index
        int right = rightChild(i);  

        // If the left child is smaller than the current
          // smallest element, update smallest
        if (left < size && heap[left] < heap[smallest]) {
            smallest = left;
        }

        // If the right child is smaller than the current
          // smallest element, update smallest
        if (right < size && heap[right] < heap[smallest]) {
            smallest = right;
        }

        // If the smallest element is not the current
          // element, swap and continue heapifying down
        if (smallest != i) {
            swap(i, smallest);
            heapifyDown(smallest);
        }
    }

    // Method to extract the minimum element from the heap
    public int extractMin() {
        if (size == 0) {
              // Check if the heap is empty
            throw new RuntimeException("Heap is empty!"); 
        }

          // The root of the heap is the minimum element
        int min = heap[0]; 
          
          // Replace the root with the last element in the heap
        heap[0] = heap[size - 1]; 
        size--; 
      
          // Restore the heap property by "heapifying down" from the root
        heapifyDown(0); 

          // Return the extracted minimum element
        return min; 
    }

    // Method to print the current
      // state of the heap
    public void printHeap() {
        // Print the heap elements as
          // an array, up to the current size
        System.out.println(Arrays.toString(Arrays.copyOf(heap, size)));
    }

    // Main method to demonstrate the
      // usage of the BinaryHeap class
    public static void main(String[] args) {
          // Create a BinaryHeap with an initial capacity of 10
        BinaryHeap bh = new BinaryHeap(10); 

        // Insert elements into the heap
        bh.insert(10);
        bh.insert(5);
        bh.insert(30);
        bh.insert(3);
        bh.insert(8);

        // Print the heap after inserting elements
        System.out.println("Heap after inserting elements:");
        bh.printHeap();

        // Extract the minimum element and print it
        System.out.println("Extracted minimum: " + bh.extractMin());
        // Print the heap after extracting the minimum element
        System.out.println("Heap after extracting the minimum:");
        bh.printHeap();
    }
}