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
    13,783
    Blog Entries
    7
    Rep Power
    21

    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
    cenosillicaphobia: the fear for an empty beer glass

  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
    13,783
    Blog Entries
    7
    Rep Power
    21

    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
    cenosillicaphobia: the fear for an empty beer glass

  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
    13,783
    Blog Entries
    7
    Rep Power
    21

    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
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Heap Sort
    By sehudson in forum New To Java
    Replies: 8
    Last Post: 03-31-2011, 04: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, 09:04 PM
  4. Heap Sort in Java
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-16-2008, 11: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
  •