2
\$\begingroup\$

This is my take on binary and ternary heapsort implementation for a university assignment. The code works but I wonder if there are any mistakes or things to improve.

class HeapSorter {

    static int[] array;
    static int heapSize;

    //=============================BINARY HEAPSORT=============================//

    static void maxHeapify(int i){

        int leftChild = left(i);
        int rightChild = right(i);
        int largest;

        largest = leftChild <= heapSize && array[leftChild] > array[i] ? leftChild : i ;

        if(rightChild <= heapSize && array[rightChild] > array[largest])
            largest = rightChild;


        if(largest != i){
            swap(i, largest);

            //Recursively heapify the subtree
            maxHeapify(largest);
        }


    }

    static void binaryHeapSort(int[] toSort){
        array = toSort;
        buildMaxHeap();

        //testing i >= 0 will be executed for i= array.length - 1, array.length - 2,......0,-1. So array.length + 1 times (n + 1)
        //i-- will be executed array.length times (n)
        for(int i = array.length - 1; i >= 0; i--){

            //swap executed n times (n)
            swap(0,i); 

            // heapSize - 1 executed n times (n)
            // assignment executed n times (n)
            heapSize = heapSize - 1; 

            //maxHeapify executed n times (n)
            maxHeapify(0); 
        }

    }

    static void buildMaxHeap(){
        heapSize = array.length - 1;
        for(int i = (array.length - 1) / 2; i >= 0; i--)
            maxHeapify(i);

    }

    static int left(int i){
        return i << 1;
    }

    static int right(int i){
        return (i << 1) + 1;
    }

    //==========================================================================//

    //=============================TERNARY HEAPSORT=============================//

    static void buildMaxHeapT(){
        heapSize = array.length - 1 ;
        for(int i =array.length - 1  / 3; i >= 0; i--)
            maxHeapifyT(i);

    }

    static void maxHeapifyT(int i){

        int leftChild = leftT(i);
        int rightChild = rightT(i);
        int middleChild = middleT(i);
        int largest;

        largest = leftChild <= heapSize && array[leftChild] > array[i] ? leftChild : i;

        if(rightChild <= heapSize && array[rightChild] > array[largest])
            largest = rightChild;

        if(middleChild <= heapSize && array[middleChild] > array[largest])
            largest = middleChild;


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

    static void ternaryHeapSort(int[] toSort){
        array = toSort;
        buildMaxHeapT();

        for(int i = array.length - 1; i >= 0; i--){
            swap(0,i); //add last element on array, i.e heap root

            heapSize = heapSize - 1; //shrink heap by 1
            maxHeapifyT(0);
        }

    }

    static int leftT(int i){
        return 3 * i + 1;
    }

    static int middleT(int i){
        return 3 * i + 2;
    }

    static int rightT(int i){
        return 3 * i + 3;
    }

    //==========================================================================//



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




    static int[] start (int[] toSort, boolean binaryHeap) {
        if (binaryHeap) {
            binaryHeapSort(toSort);
        } else { 
            ternaryHeapSort(toSort);
        }

        return toSort;
    }
}

Also, should I use bit shifting like this:

static int leftT(int i){
    return (i << 1) + i + 1;
 }

instead of

static int leftT(int i){
    return 3 * i + 1;
}
\$\endgroup\$
2
\$\begingroup\$

It's not bad. And I'm lazy, so just two comments:

static int[] array;

No statics should be ever used except for constants. Please always create an object, ideally assign everything in the constructor, and let it work on its data.

It's just a few lines more and it makes your class much more usable. Statics are sort of global variables, which means bad. The way you did it, it works... but try to start more threads and call start concurrently.

Also should i use bit shifting like this:

No, except maybe on Android. Let the JVM do its work. It probably knows much more tricks than you (e.g., doing x / 10 without division instruction, i.e., maybe 3 times faster).

\$\endgroup\$
2
  • \$\begingroup\$ you are right about the static but it has to be this way because the methods have to be static. This is for evaluation purposes. I mean, i was asked for this. \$\endgroup\$ – qbit Sep 20 '14 at 1:11
  • \$\begingroup\$ @xgeorgekx If you were asked to make it static, then it's to be made static, alright. But note that nothing really has to be static, you can always create your object, let it do its job, and wrap it all into a static method for easy of use (like staticSort(Some data) {return new Sorter(data).doItAll();}). \$\endgroup\$ – maaartinus Sep 20 '14 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.