MIN HEAP USING JAVA

• In Min heap, we have to add element such that parent has minimum value than it’s child value.

• Here we represent Min heap as tree and we are going to implement it with static array in which zero index has no value. We add value in array starting from index one as show in figure.

• Here we have same concept of queue that FIFO(first in – first out)

Functionality :-

• Enqueue – Add element at last.

• Dequeue – Delete from first position.

• Peek – Display First Element 

Advantage of Min heap:- Sorting become more efficient.

Enqueue :-

• Suppose if we want to add 1 in upper Min heap than we have to add 1 at index 11 (suppose index 11 is there.).But as we know Min heap means child has maximum value that it’s parent but here 1<3, which is not possible that we have to swap that two value. For that what can do that Number[i/2]<->Number[i], means as we can here we have index 11 if take 11/2=5(in integer) than you can directly jump at it’s parent value and exchange that value. After exchanging that two value you will again find that 1<2 that again you can change that value with upper logic like this we have to move untill we don’t find that Number[i/2]>Number[i].

Dequeue:-

• As we know for dequeue, we have to remove element from root or from first position for that we have to move last element of array (here we have 1) at first position but still parent should have minimum value than child for that we have compare Number[i] with Number[2*i] and Number[2*i+1] because of you again go through upper image than you will that parent (Number[i]) has two child Number[2*i] and Number[2*i+1].So we have to compare that value and if you find and minimum value of child than parent that swap those two value.

Peek:-

• In peek we have where first element of array or tree.

Algorithm Of Min heap

import java.util.Scanner; class MinPriorityQueue { private int []Number;///Array to store data private int MAXI;//Maximum size of static array private int size;//number of element in list public MinPriorityQueue(){}//construtor public MinPriorityQueue(int maxi)//parameterized construtor { size=0; MAXI=maxi; Number=new int[maxi+1]; } public void Enqueue(int Item)//Add element in min priority queue { if(size<MAXI) { if(size==0) { size++; Number[size]=Item; } else { size++; if(Item>=Number[size/2]) { Number[size]=Item; } else { int i=size; Number[i]=Item; while(true) { if(i==1){break;} if(Number[i]<Number[i/2]) { int Temp=Number[i/2]; Number[i/2]=Number[i]; Number[i]=Temp; i=i/2; } else { break; } } } } } else { System.out.println("\nMIN PRIORITY QUEUE IS FULL.\n"); } } public int Dequeue()//delete root or first element { if(size==0) { return -999; } else { int RemovedElement=Number[1]; Number[1]=Number[size]; size--;int i=1; while(true) { if(i>=size){break;} if(2*i+1<=size) { if(Number[2*i]<Number[i]) { int Swapper=Number[i]; Number[i]=Number[2*i]; Number[2*i]=Swapper; } if(Number[2*i+1]<Number[i]) { int Swapper=Number[i]; Number[i]=Number[2*i+1]; Number[2*i+1]=Swapper; } i=i*2; } else if(2*i<=size) { if(Number[2*i]<Number[i]) { int Swapper=Number[i]; Number[i]=Number[2*i]; Number[2*i]=Swapper; i=i*2; } else { break; } } else { break; } } return RemovedElement; } } public int Peek()//display first value of array { if(size==0) { return -999; } else { return Number[1]; } } public void Display() { for(int i=1;i<=size;i++) { System.out.println(Number[i]); } } } class MinPriority_Queue { public static void main(String[] args) { MinPriorityQueue m=new MinPriorityQueue(10); m.Enqueue(6); m.Enqueue(2); m.Enqueue(10); m.Enqueue(3); m.Enqueue(9); m.Enqueue(15); m.Enqueue(74); m.Enqueue(4); m.Enqueue(65); m.Enqueue(45); m.Display(); System.out.println("\nDeleted Element :- "+m.Dequeue()); m.Display(); System.out.println("\t\t\tSorted List"); while(m.Peek()!=-999) { System.out.println("\t\t\t"+m.Dequeue()); } } }

Download :- Min Heap