Results 1 to 6 of 6
Thread: heap sort help
 12052011, 12:53 PM #1Senior Member
 Join Date
 Nov 2010
 Posts
 155
 Rep Power
 7
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); } } }
please can someone tell me where have I gone wrong???
NOTE: the algorithm assumed the array is 1based indexing
 12052011, 01:40 PM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,414
 Blog Entries
 7
 Rep Power
 25
 12052011, 03:13 PM #3Senior Member
 Join Date
 Nov 2010
 Posts
 155
 Rep Power
 7
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?
 12052011, 04:25 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,414
 Blog Entries
 7
 Rep Power
 25
Re: heap sort help
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,
JosBuild a wall around Donald Trump; I'll pay for it.
 12052011, 04:31 PM #5Senior Member
 Join Date
 Nov 2010
 Posts
 155
 Rep Power
 7
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
 12052011, 04:33 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,414
 Blog Entries
 7
 Rep Power
 25
Similar Threads

Heap Sort
By sehudson in forum New To JavaReplies: 8Last Post: 03312011, 03:25 AM 
Using Merge Sort to sort an ArrayList of Strings
By coldfire in forum New To JavaReplies: 3Last Post: 03132009, 02:03 AM 
How to sort a list using Bubble sort algorithm
By Java Tip in forum AlgorithmsReplies: 3Last Post: 04292008, 08:04 PM 
Heap Sort in Java
By Java Tip in forum AlgorithmsReplies: 0Last Post: 04162008, 10:27 PM 
Heap Sort
By kesav2005 in forum Advanced JavaReplies: 1Last Post: 11132007, 12:40 PM
Bookmarks