HEAP SORT HELP

[spidey12345]

Here is what i wrote for heap sort


//heapSort method
public static void heapsort(float[] array)
{
int n = array.length-1;
BuildMaxHeap(array);
while(n>=2){
swap(array, 1, n);
n--;
}

maxHeapfy(array, 1);
}

private static void maxHeapfy(float[] array, int i)
{
int n = array.length-1;

int largest = i;
int l = 2*i;
int r = 1+2*i;

if ( l <= n && array[l] >=array[largest]) {
largest = l;
}
if ( r <= n && array[r] >=array[largest] ) {
largest = r;
}

if ( largest != i ) {
swap(array, largest, i);
maxHeapfy(array, largest);
}

}

private static void BuildMaxHeap(float[] array)
{
int n = array.length-1;
for(int i = n/2; i>=1; i--)
maxHeapfy(array, i);
}

private static void swap(float array[], int i, int j)
{
float t=array;
array=array[j];
array[j]=t;
}



when i run a float array with = { 0.12, 0.67, 0.57, 0.64, 0.93}


it gives me wrong output of 0.64, 0.57, 0.67, 0.12, 0.93} Anybody know
where my aglorithm is wrong at

by the way, the array is 0-20
so i ingored the first 0 index, and go from 1-20...
and i copy the 0-19 original array to the 1-20 copied array, and sort
the copied array... so i don't think there is anything wrong with the
starting indexes, PLZ HELP, if you can tell me where the error is at...

 

[Joshua Cranmer]

1. Don't shout; it gets quicker answers;
2. This is not an IM; proper grammar, spelling, punctuation, and
capitalization are useful tools here.
3. Here's your problem(s):

Here is what i wrote for heap sort


//heapSort method
public static void heapsort(float[] array)
{
int n = array.length-1;
BuildMaxHeap(array);
while(n>=2){
swap(array, 1, n);
n--;
}
maxHeapfy(array, 1);
}

What this code does is builds a heap, moves the largest element to the
end, and swaps some stuff within the heap and reheapifies the invalid
heap. What you're missing is that a heap has to be re-heapified after
each removal. It should look more like this:
public static void heapsort(float[] array)
{
int n = array.length-1;
BuildMaxHeap(array);
while (n >=2) {
swap(array, 1, n--);
maxHeapify(array, 1, n);
}
}

maxHeapify (there's an `i' you know) should look like this:
private static void maxHeapify(float[] array, int i, int n)
{
int largest = i, l = 2*i, r = 2*i+1;
if (l <= n && array[l] >= array[largest])
largest = l;
if (r <= n && array[r] >= array[largest])
largest = r;
if (largest != i) {
swap(array, largest, i);
maxHeapify(array, largest, i);
}
}

private static void BuildMaxHeap(float[] array)
{
int n = array.length-1;
for(int i = n/2; i>=1; i--)
maxHeapfy(array, i);
}

This code appears to be correct, except that maxHeapfy(array, i) should
be maxHeapify(array, i, n);

private static void swap(float array[], int i, int j)
{
float t=array;
array=array[j];
array[j]=t;
}

No problems here. :-D

when i run a float array with = { 0.12, 0.67, 0.57, 0.64, 0.93}

you should get {0.12, 0.57, 0.64, 0.67, 0.93}. Barring any stupid errors
on my part, this should work.