Am trying to implement min Heap using arrays. The problem am facing is when i poll an element technically it should return an minimum element from the Heap.
But using the code i wrote it doesn't gives the minimum element
Output:
inserted heap: 1 3 2 6 4 5
Polledvlaue : 1
New Heap after poll : 3 5 2 6 4
Polled value :3
New Heap after poll : 4 5 2 6
Polled value :4
New Heap after poll : 5 6 2
Required output:
when polled it should give minimum Value
Main class code:
public class HeapApp {
public static void main(String[] args) {
Heap hg = new Heap(6);
hg.insert(6);
hg.insert(5);
hg.insert(4);
hg.insert(3);
hg.insert(2);
hg.insert(1);
System.out.print("inserted heap: ");
hg.print();
System.out.println();
System.out.println("Polledvlaue : "+hg.poll());
System.out.print("New Heap after poll : ");hg.print();
System.out.println();
System.out.println("Polled value :"+hg.poll());
System.out.print("New Heap after poll : "); hg.print();
System.out.println();
System.out.println("Polled value :"+hg.poll());
System.out.print("New Heap after poll : ");hg.print();
}
}
Heap Class:
public class Heap {
private int heapSize;
private int arr[];
Heap(int capacity){
heapSize = 0;
arr = new int[capacity];
}
public boolean isFull() {
return heapSize == arr.length;
}
public boolean isEmpty() {
return heapSize == 0;
}
public void insert(int element) {
if(isFull()) {
throw new RuntimeException("Heap is full");
}
arr[heapSize] = element;
heapSize++;
heapifyUp();
}
private void heapifyUp() {
int index = heapSize-1;
while(index > 0 ) {
if( arr[(index-1)/2] > arr[index]) {
int temp = arr[index];
arr[index] = arr[(index-1)/2];
arr[(index-1)/2] = temp;
index = (index-1)/2;
}else {
break;
}
}
}
public int poll() {
if(isEmpty())
throw new RuntimeException("Heap is empty");
int ans = arr[0];
arr[0] = arr[heapSize-1];
heapSize--;
heapifyDown();
return ans;
}
private void heapifyDown() {
int index = 0;
int left = 2*index+1;
while(left < heapSize) {
int min = left ; int right = ++left;
if(right < heapSize) {
if(arr[left] > arr[right]) {
min++;
}
}
if(arr[index] > arr[min]) {
int temp = arr[min];
arr[min] = arr[index];
arr[index] = temp;
}
index = min;
left = 2*index+1;
}
}
public void print() {
for(int i = 0 ; i < heapSize ; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
private void heapifyDown() {
int index = 0;
int left = 2*index+1;
while(left < heapSize) {
int min = left ; int right = ++left; // <------ Here's your bug.
if(right < heapSize) {
if(arr[left] > arr[right]) {
min++;
}
}
if(arr[index] > arr[min]) {
int temp = arr[min];
arr[min] = arr[index];
arr[index] = temp;
}
index = min;
left = 2*index+1;
}
}
The ++left is incrementing both left and right to the same value.
Change that to int right = left + 1;