CODEWITHSUNDEEP
javaalgorithmheapsort
user1010101
user1010101

Reputation: 1658

What is the correct way of implementing the heapsort?

I spend last 5 hours looking at so many videos and readings (cormen included) and i finally decided to write my own heapsort to test it out. I am basically taking some inputs from standard input and storing them in an array and then i will use heapsort to sort them.

Following is my code

 public static void buildHeap(int[] A)
     {
         n = A.length - 1;
         for(int i = n/2; i>0; i--)
         {
             maxHeapify(A,i);
         }
     }

     public static void maxHeapify(int[] A, int i)
     {
         int left = 2*i;
         int right = 2*i + 1;
         int largest = 0;
         if(left <= n && A[left] > A[i])
            {
                largest=left;
            }
            else
            {
                largest=i;
            }

            if(right <= n && A[right] > A[largest]){
                largest=right;
            }
            if(largest!=i){
                int temp = A[i];
                A[i] = A[largest];
                A[largest] = temp;
                maxHeapify(A, largest);
            }
        }

My Array Input is : 3,5,8,7,1,13,11,15,6 Output is: 3,15,13,11,6,8,5,7,1

The output is obviously wrong as the first index should contain the highest value 15.

So then i decided to take the good old route of taking a pen and a notebook and tracing the code and realized that in the buildHeap the i should be n-1/2 . However it also did not give me the correct output. I am really lost now and frustrated. Can anyone shed light as to what i am doing wrong?

Upvotes: 1

Views: 787

Answers (1)

Stack Exchange Broke The Law
Stack Exchange Broke The Law

Reputation: 58929

Your index calculations are off:

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

If i is 0, then we want left and right to be 1 and 2. If i is 1, then left and right should be 3 and 4, and so on. The calculations should be:

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

Also,

for(int i = n/2; i>0; i--)

The condition is i > 0. The body of the loop will only run when i > 0, so the element at index 0 (i.e. the first one) won't get moved. The condition should be i >= 0.

Upvotes: 2

Related Questions