Results 1 to 6 of 6

Thread: heap sort help

  1. #1
    aizen92 is offline Senior Member
    Join Date
    Nov 2010
    Posts
    155
    Rep Power
    5

    Default 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. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,050
    Blog Entries
    7
    Rep Power
    23

    Default Re: heap sort help

    Quote Originally Posted by aizen92 View Post
    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
    The only person who got everything done by Friday was Robinson Crusoe.

  3. #3
    aizen92 is offline Senior Member
    Join Date
    Nov 2010
    Posts
    155
    Rep Power
    5

    Default 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. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,050
    Blog Entries
    7
    Rep Power
    23

    Default Re: heap sort help

    Quote Originally Posted by aizen92 View Post
    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
    The only person who got everything done by Friday was Robinson Crusoe.

  5. #5
    aizen92 is offline Senior Member
    Join Date
    Nov 2010
    Posts
    155
    Rep Power
    5

    Default 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. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,050
    Blog Entries
    7
    Rep Power
    23

    Default Re: heap sort help

    Quote Originally Posted by aizen92 View Post
    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
    The only person who got everything done by Friday was Robinson Crusoe.

Similar Threads

  1. Heap Sort
    By sehudson in forum New To Java
    Replies: 8
    Last Post: 03-31-2011, 03:25 AM
  2. Using Merge Sort to sort an ArrayList of Strings
    By coldfire in forum New To Java
    Replies: 3
    Last Post: 03-13-2009, 02:03 AM
  3. How to sort a list using Bubble sort algorithm
    By Java Tip in forum Algorithms
    Replies: 3
    Last Post: 04-29-2008, 08:04 PM
  4. Heap Sort in Java
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-16-2008, 10:27 PM
  5. Heap Sort
    By kesav2005 in forum Advanced Java
    Replies: 1
    Last Post: 11-13-2007, 12:40 PM

Posting Permissions

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