CODEWITHSUNDEEP
javaalgorithmdata-structuresheapbinary-heap
Mona Jalal
Mona Jalal

Reputation: 38165

Max Heap is not working as expected

My Java code for Max Heap is not working as expected. Also it is not returning 90 as max when I remove from heap. 

/**
 * Created by mona on 5/25/16.
 */
public class Heap {
    private int[] heap;
    private int size;
    private int maxSize;


    public Heap(int maxSize) {
        this.maxSize=maxSize;
        this.size=0;
        heap=new int[this.maxSize+1];
    }

    private int parent(int pos) {
        return pos/2;
    }

    private int leftChild(int pos) {
        return pos*2;
    }

    private int rightChild(int pos) {
        return pos*2 +1;
    }

    private boolean isLeaf(int pos) {
        if (pos>=size/2 && pos<=size) {
            return true;
        }
        return false;
    }

    private void swap(int pos1, int pos2) {
        int tmp=heap[pos1];
        heap[pos1]=heap[pos2];
        heap[pos2]=tmp;
    }


    private void maxHeapify(int pos) {
        if (!isLeaf(pos)){
            if ((heap[pos] < heap[leftChild(pos)]) ||
               (heap[pos] < heap[rightChild(pos)])) {
            if (heap[leftChild(pos)] > heap[rightChild(pos)]) {
                swap(pos , leftChild(pos));
                maxHeapify(leftChild(pos));
            }
            else {
                swap(pos , rightChild(pos));
                maxHeapify(rightChild(pos));
            }

            }

        }
    }

    public void maxHeap() {
        for (int i=(size/2) ; i>=1 ; i--) {
            maxHeapify(i);
        }
    }

    public void insert(int n) {
        heap[++size] = n;
        int tmpLocation = size;
        while (heap[tmpLocation] > heap[parent(tmpLocation)]){
            swap(tmpLocation , parent(tmpLocation));
            tmpLocation=parent(tmpLocation);
        }


    }

    public int remove() {
        int removed = heap[1];
        heap[1] = heap[size-1];
        maxHeapify(1);
        return removed;
    }

    public void print() {
        for (int i=1 ; i<=(size/2) ; i++) {
            System.out.println("current node is: "+heap[i]+" its left child is " +
                    heap[i*2]+" its right child is "+heap[i*2 +1]);
        }

    }

    public static void main(String[] args) {
        Heap heap = new Heap(9);
        heap.insert(8);
        heap.insert(18);
        heap.insert(28);
        heap.insert(9);
        heap.insert(12);
        heap.insert(90);
        heap.insert(1);
        heap.insert(87);
        heap.maxHeap();

        heap.print();
        System.out.println("Max is: "+heap.remove());

    }


}

Here's the output:

current node is: 90 its left child is 90 its right child is 87
current node is: 87 its left child is 28 its right child is 18
current node is: 28 its left child is 12 its right child is 9
current node is: 18 its left child is 8 its right child is 1
current node is: 12 its left child is 0 its right child is 0
Max is: 87

Process finished with exit code 0

Also you can see in the first line of output it states left child of 90 is 90 which isn't right. What is that?

current node is: 90 its left child is90 its right child is 87

UPDATE: When I set the size to 8 I get this error:

Exception in thread "main" current node is: 90 its left child is90 its right child is 87
current node is: 87 its left child is28 its right child is 18
current node is: 28 its left child is12 its right child is 9
current node is: 18 its left child is8 its right child is 1
java.lang.ArrayIndexOutOfBoundsException: 9
    at Heap.print(Heap.java:86)
    at Heap.main(Heap.java:104)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:497)
    at com.intellij.rt.execution.application.AppMain.main(AppMain.java:144)

Process finished with exit code 1

UPDATE: I thought if I change the insert to the following would help but no:

public void insert(int n) {
        size++;
        heap[size] = n;
        int tmpLocation = size;
        if (tmpLocation!=1) {
            while (heap[tmpLocation] > heap[parent(tmpLocation)]) {
                swap(tmpLocation, parent(tmpLocation));
                tmpLocation = parent(tmpLocation);
            }
        }


    }

Upvotes: 0

Views: 909

Answers (2)

Jim Mischel
Jim Mischel

Reputation: 134005

In your insert and remove methods, the code assumes that the root node is at heap[1]. But your print method thinks that the root node in your heap is at heap[0]. That's going to lead you into all kinds of trouble.

Note also that your remove method doesn't decrement size.

Upvotes: 1

attaboy182
attaboy182

Reputation: 2079

The culprit is this line:

heap[++size] = n;

When you're inserting the first element, you're inserting at position 1, and with the steps you perform, heap[0] & heap[1] will end up having the same values after every insertion. That's why you'll see parent and left child having the same value after every insertion.

For example, when you're inserting the first element, you try to insert at heap[1], and perform swap between heap[0] & heap[1]. The result is you end up with same values in heap[0] & heap[1].

Upvotes: 1

Related Questions