CODEWITHSUNDEEP
javadata-structures
Satya
Satya

Reputation: 8881

creating a max-heap using java

I am trying to create a Max-Heap in java using the following code:

public class Heapify {
// 16 14 10 8 7 9 3 2 4 1

    public static int[] Arr = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
    public static int counter = 0;

    public static void main(String[] args) {
        int kk;
        for (kk = 0; kk <= Arr.length - 1; kk++) {
            heapM(Arr, kk);
        }

        for (int krk = 0; krk < Arr.length; krk++) {
            System.out.println(Arr[krk]);
        }



    }

    public static void heapM(int[] Arr, int i) {

        int largest;
        int left = i * 2;
        int right = i * 2 + 1;
        if (((left < Arr.length) && (Arr[left] > Arr[i]))) {
            largest = left;
        } else {
            largest = i;
        }

        if (((right < Arr.length) && (Arr[right] > Arr[largest]))) {
            largest = right;
        }
        if (largest != i) {
            swap(i, largest);


            heapM(Arr, largest);
        }
    }

    private static void swap(int i, int largest) {
        int t = Arr[i];
        Arr[i] = Arr[largest];
        Arr[largest] = t;

    }
}

The desired output should be :

16 14 10 8 7 9 3 2 4 1

Whereas I am getting 

4 3 16 14 8 9 10 2 1 7

Can someone please help as to why the heap is not being built properly ?

Thanks

Upvotes: 2

Views: 24730

Answers (5)

stones333
stones333

Reputation: 8958

for (kk = Arr.length -1; kk >= 0; kk--) {
    heapM(Arr, kk);
}

should be 

for (kk = (Arr.length -1)/2; kk >= 0; kk--) {
    heapM(Arr, kk);
}

More efficient.

Edit This lets you build a heap in O(n) time instead of O(n*lg(n)) time and is explained here: http://en.wikipedia.org/wiki/Binary_heap#Building%5Fa%5Fheap

Upvotes: 2

javanx
javanx

Reputation: 698

Is this a homework? If not you can use PriorityQueue of JAVA

Upvotes: 1

Egalitarian
Egalitarian

Reputation: 2218

As you want to make a max-heap, you should start from n/2 down to 0 instead of 0 to n. Due to 0 to n what happens is that say in an array like 2 0 1 12 13. The output array after you perform max heap will be 2 13 1 12 0 where as if you call from n/2 down to 0 it will be 13 12 1 2 0.

Upvotes: 1

La bla bla
La bla bla

Reputation: 8708

I ran your code, and in addition to what Jodaka said, I found one more error

for (kk = 0; kk <= Arr.length - 1; kk++) {
        heapM(Arr, kk);
}

should be

for (kk = Arr.length -1; kk >= 0; kk--) {
        heapM(Arr, kk);
}

because when doing MaxHepify, you start from the end, and go backwards. and

 int left = i * 2;
 int right = i * 2 + 1;

should be, as Jodaka said

int left = 2*i+1;
int right = 2*i + 2;

I ran it here and the output is now correct

Upvotes: 6

Jodaka
Jodaka

Reputation: 1247

I think your problem is here:

int left = i * 2;
int right = i * 2 + 1;

Since java arrays are zero-based, you are saying that the left child of 0 is 0 * 2 = 0! Fix your logic and see if that fixes your problem.

Upvotes: 4

Related Questions