Min Heap

Also Read

Min Heap

A Min-Heap is a complete binary tree in which each internal node's value is less than or equal to the value of that node's children. The heap element to array element mapping is straightforward: if a node is stored at index a, its left child is stored at index 2a + 1 and its right child is stored at index 2a + 2.

In today's article we will see about min heap binary tree and also write a complete min heap program with the help of which we can perform CURD operations easily.

Min Heap Binary Tree

We represent the min heap binary tree in the form of an array and its elements are in the format as shown below.

• Current Node: array[i]
• Parent Node: array[(i-1)/2]
• Left Child: array[i*2+1]
• Right Child: array[i*2+2]

Min Heap In Java

public class MinHeap {

	int[] arr = new int[20];
	int index=-1;
		
	
	//This function will insert the value at the end of the
	//array and then compare it with its parent node and if 
	//it is bigger than its parent node then let it remain as
	//it is otherwise we have to fix the property of heap.
	public void insertValue(int v) {
		index++;
		arr[index]=v;
		int i=index;
		
		while(i!=0) {
			int parent = (i-1)/2;
			if(arr[parent] > arr[i]) {
				int temp = arr[parent];
				arr[parent] = arr[i];
				arr[i] = temp;
				i=parent;
			}else {
				break;
			}
		}
		System.out.println("Value has been inserted successfully!");
	}
	
	
	
	//Display all the values in an array
	public void display() {
		for(int i=0;i<=index;i++) {
			System.out.print(arr[i]+", ");
		}
		System.out.println();
	}
	
	
	
	//This function will return true if the node has no child
	//otherwise it will return false.
	private boolean isleaf(int i) {
		if(2*i+1>index) {
			return true;
		}
		else {
			return false;
		}
	}
	
	
	
	//This function will compare left child and right child 
	//and return the index of whichever is smaller.
	private int minimum(int leftchild, int rightchild) 
	{
		if(arr[leftchild]<arr[rightchild] || (rightchild*2)+1 > index) {
			return leftchild;
		}else {
			return rightchild;
		}
	}
	
	
	
	
	//delete the minimum value from MinHeap 
	public void delete() {
		arr[0] = arr[index];
		index--;
		
		int i=0;
		
		while(i!=index) {
			int leftchild = (i*2)+1;
			int rightchild = (i*2)+2;
			int minimum = minimum(leftchild,rightchild);
			if(arr[i] > arr[minimum]) {
				int temp = arr[minimum];
				arr[minimum] = arr[i];
				arr[i] = temp;
				i=minimum;
			}else {
				break;
			}
		}
	}
    
	
	//main function
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int choice;
		MinHeap obj = new MinHeap();
		while(true) {
			System.out.println("\n1. Insert value in MinHeap\n2. Display all values\n3. Delete minimum value\n4. Exit");
			choice = scanner.nextInt();
			switch(choice) {
			case 1:{
				System.out.print("\nEnter value : ");
				int value = scanner.nextInt();
				obj.insertValue(value);
				continue;
			}
			case 2:{
				obj.display();
				continue;
			}
			case 3:{
				obj.delete();
				continue;
			}
			case 4:{
				break;
			}
			}
			break;
		}
	}
}

Output

After writing the code, compile the program and if any issue comes, you can comment us or you can watch a video on this topic on our YouTube Channel