Binary Heap (Heapify and Extract)

Tue Feb 08 2022 15:25:57 GMT+0000 (UTC)

```import java.util.*;
import java.io.*;

class Test {

public static class MinHeap
{
int arr[];
int size;
int capacity;

MinHeap(int c){
size = 0;
capacity = c;
arr = new int[c];
}

int left(int i) { return (2*i + 1); }
int right(int i) { return (2*i + 2); }
int parent(int i) { return (i-1)/2; }

public void insert(int x)
{
if (size == capacity)return;
size++;
arr[size-1]=x;

for (int i=size-1;i!=0 && arr[parent(i)]>arr[i];)
{
int temp = arr[i];
arr[i] = arr[parent(i)];
arr[parent(i)] = temp;
i = parent(i);
}
}

public void minHeapify(int i)
{
int lt = left(i);
int rt = right(i);
int smallest = i;
if (lt < size && arr[lt] < arr[i])
smallest = lt;
if (rt < size && arr[rt] < arr[smallest])
smallest = rt;
if (smallest != i)
{
int temp = arr[i];
arr[i] = arr[smallest];
arr[smallest] = temp;
minHeapify(smallest);
}
}

public int extractMin()
{
if (size <= 0)
return Integer.MAX_VALUE;
if (size == 1)
{
size--;
return arr[0];
}
int temp = arr[0];
arr[0] = arr[size-1];
arr[size-1] = temp;
size--;
minHeapify(0);

return arr[size];
}

}

public static void main(String args[])
{
MinHeap h=new MinHeap(11);
h.insert(3);
h.insert(2);
h.insert(15);
h.insert(20);
System.out.print(h.extractMin());     // OUTPUT : 2
}
} ```
content_copyCOPY