heap sort help

[aizen92]

Hello, I am trying to implement heap sort using an algorithm, and i was able to write the code, and i think it is correct, but when trying to output it it gives me the same array, for more details check the pic below

this is the code i wrote:

import java.util.Arrays;

public class Heap
{
    public static void main (String[] args)
    {
        int [] a = {7, 4, 3, 1, 2};
        
        buildMaxHeap(a);
    }
    
    public static void buildMaxHeap (int[] a)
    {        
        System.out.println(Arrays.toString(a));
        
        int len = a.length;
        
        for (int i = len / 2; i >= 0; i--)
        {
            maxHeapify(a, i, len);
        }
        
        System.out.println(Arrays.toString(a));
    }
    
    public static void maxHeapify (int[] a, int i, int n)
    {
        int largest;
        
        int left = 2 * i;
        int right = (2 * i) + 1;
        
        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, n);
        }
    }
}

and the result is in the pic below :



please can someone tell me where have I gone wrong???

NOTE: the algorithm assumed the array is 1-based indexing

[JosAH]

NOTE: the algorithm assumed the array is 1-based indexing

That's where you go wrong: arrays are zero based indexed, so for a node at index location i its two childs are at locations 2*i+1 and 2*i+2.

kind regards,

Jos

[aizen92]

Thnx Jos for the quick help, but unfortunately it didnt work.
I'm not sure, but I think im having an error of referencing the array a, or am I wrong?

[JosAH]

Thnx Jos for the quick help, but unfortunately it didnt work.
I'm not sure, but I think im having an error of referencing the array a, or am I wrong?

Your algorithm isn't correct; you're only executing 'phase1' of the heap sort algorithm. It guarantees that the largest element is at location #0. You should swap it with the element at the end, reduce the heap size by one and 'reheapify' the heap starting at location #0. I wrote a blog article on heap sort once (my implementation can sort anything). See near the top of this page for the 'Blogs' button; you'll find the article.

kind regards,

Jos

[aizen92]

Thanks again Jos for the help, I'm starting to get glimpse of what I was doing wrong, I'll continue reading the article, and fix my code
Thanks alot

[JosAH]

Thanks again Jos for the help, I'm starting to get glimpse of what I was doing wrong, I'll continue reading the article, and fix my code
Thanks alot

Well, you didn't do anything wrong (except for those indexes in your op); you just forgot to implement 'phase 2' of the algorithm (see my blog article).

kind regards,

Jos