# heap sort help

• 12-05-2011, 12:53 PM
aizen92
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:

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 :

http://i43.tinypic.com/31293li.png

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

NOTE: the algorithm assumed the array is 1-based indexing
• 12-05-2011, 01:40 PM
JosAH
Re: heap sort help
Quote:

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
• 12-05-2011, 03:13 PM
aizen92
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?
• 12-05-2011, 04:25 PM
JosAH
Re: heap sort help
Quote:

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
• 12-05-2011, 04:31 PM
aizen92
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
• 12-05-2011, 04:33 PM
JosAH
Re: heap sort help
Quote:

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