0

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();
    }
    
}
1
  • in method heapifyDown() int right = ++left is this correct here?, left would be always on same position of right with this statement. Better used int right = left + 1 Commented Aug 18, 2020 at 13:03

1 Answer 1

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

Sign up to request clarification or add additional context in comments.

3 Comments

Thanks, But Could you Explain with 1 example, Cuz when we pre-increment say left it would first be incremented and then stored the incremented value in right. So here You Meant tp say that, ++left is actually left=left+1 and then storing that left value in right.
No. When you do right = ++left, it first increments left and stores it in left. It then copies the new value of left to right. So left and right become the SAME value. When we do right = left + 1, then left and right are DIFFERENT values.
Thank You, Got it!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.