1. Senior Member
Join Date
Nov 2010
Posts
155
Rep Power
8

## heap sort help

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:

Java Code:
```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

2. ## Re: heap sort help

Originally Posted by aizen92
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

3. Senior Member
Join Date
Nov 2010
Posts
155
Rep Power
8

## Re: heap sort help

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?

4. ## Re: heap sort help

Originally Posted by 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?
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

5. Senior Member
Join Date
Nov 2010
Posts
155
Rep Power
8

## Re: heap sort help

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

6. ## Re: heap sort help

Originally Posted by 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
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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•