Search code examples
javadata-structuresheapmin-heap

Min Heap implementation using Arrays in java


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();
    }
    
}

Solution

  • 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;