1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

HeapSort Java

  1. Jan 6, 2014 #1
    1. The problem statement, all variables and given/known data
    Develop a Heapsort algorithm using java



    2. Relevant equations



    3. The attempt at a solution

    I have been trying to implement HeapSort in java. Unfortunately I am running into errors. I am printing out the index values and they go up then down and the code does not sort properly. Can you help me understand why the index values decease. Thanks.

    This comment explains how I find the final node before switching the values

    // log base 2 of (a.length - index) - truncating to get the int value - gives the length of the tree. 2^(treelength) - 1 gives the position of the final node that will be evaluated before the top value is swapped with the bottom value

    The full code is here or below

    http://pastebin.com/7tvTc4Nb


    Code (Text):

        public static void heapSort(double [] a, int node, int index){
            System.out.println("made it");
            int finalnode = 0;
            int treelength = 0;
            treelength = (int)((Math.log(a.length-index))/(Math.log(2)));

            finalnode = Math.pow(2,treelength) - 1;// log base 2 of (a.length - index) - truncating to get the int value - gives the length of the tree. 2^(treelength) - 1 gives the position of the final node that will be evaluated before the top value is swapped with the bottom value
           
           
            System.out.println("THe Finalnode is " + finalnode);
            System.out.println("The index is " + index);
            if(!(node > finalnode-1) && node >= 0 && index < a.length){
                System.out.println("in");
                boolean switchval = false;
                double holder = 0;
               
               
                if(node == finalnode){
                    switchval = true;
                }      
                if(minNode(a,node,index) != -1){
                    fixHeap(a,node, index);
                }
                if(switchval){
                    System.out.println("Switch");
                    holder = a[0];
                    a[0] = a[a.length-(1+index)];
                    a[a.length-(1+index)] = holder;
                    index++;
                    heapSort(a,0,index);       
                }
                else{
                    heapSort(a,(2*node) +1,index);
                    heapSort(a,(2*node) +2,index);
                    }
            }      
        }//heapSort
       
       
        public static int minNode(double [] a, int node,int index){
            double min;
            int pos;
            if((2*node + 1) < a.length - index){
                if((2*node + 2) < a.length - index){
                    if(a[(2*node + 1)] > a[(2*node + 2)]){
                        min = a[(2*node + 2)];
                        pos = (2*node + 2);
                    }
                    else{
                        min = a[(2*node + 1)];
                        pos = (2*node + 1);

                    }
                   
                    if(a[node] < min){
                        return (-1);
                    }
                    else{
                        return pos;
                    }
                   
                }// if 2nd child exists
                min = a[(2*node + 1)];
                pos = (2*node + 1);
                if(a[node] < min){
                        return (-1);
                    }
                else{
                    return pos;
                }
            }// if 1st child exists
            return -1; 
        }//testNode
       
        public static void fixHeap(double [] a, int node, int index){
            int test = node;
            int minNode = 0;
            double holder;
            int counter = 0;
            while(true){   
               
                counter++;
                if(test >= 0){
                    minNode = (minNode(a,test, index));
                    if(minNode == -1){
                        break;
                    }
                    holder = a[test];
                    a[test] = a[minNode];
                    a[minNode] = holder;
                    test = (test-1)/2;
                }
                else{              
                    break;
                }
            }      
        }//fixHeap
     
    Last edited by a moderator: Jan 6, 2014
  2. jcsd
  3. Jan 8, 2014 #2
    My suggestion for debugging this is to take a small example (say an array of 8 unsorted values) and work out exactly what you expect to be done by hand.
    Then put a break point in the two places code where "holder" is set and see exactly what is happening.

    On a quick look at your code, the only thing that alarmed me was the computation of treelength. Let's say that (a.length-index) is 8. What would keep treelength from being (int)2.999999999?
     
  4. Jan 9, 2014 #3
    Also, I'm guessing that you enter this routine with this call:
    heapSort(a, 0, 0)

    I would suggest renaming heapSort to nodeSort and then creating a new heapSort with this interface:

    public static void heapSort(double [] a)
     
  5. Jan 9, 2014 #4

    jedishrfu

    Staff: Mentor

    Do you have an IDE like eclipse or netbeans? They provide an interactive debugger that can walk you thru the code line by line and you can inspect the value of your variables... It's definitely something to spend some time as it will improve your programming skill and will be useful in the future.

    I use netbeans extensively at work and the debugger is just indispensable.

    Have you looked at other heap sort implementations on the web? Reviewing them might elicit what is happening in your code.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: HeapSort Java
  1. Animation in Java (Replies: 1)

  2. String in java (Replies: 7)

  3. Java program (Replies: 3)

  4. Java prob. (Replies: 1)

Loading...