# Binary HeapSort and Ternary HeapSort implementation

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);
}

}
}


Also, should I use bit shifting like this:

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


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


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).

• 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. Sep 20, 2014 at 1:11
• @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();}). Sep 20, 2014 at 8:28