# HeapSort Efficiency

For heap (array based) sort, we need to start at index 1, ignoring the 0th index. If I want to make a static function like

public static void heapSort(int[] array){ }


The user shouldn't care about leaving the 0th index empty. And I don't want to allocate a new array (only to start from the 1st index). What would be the correct way to heap sort in this case?

class Heap {

private static int[] array;
private static int heap_size;

private static int leftChild(int node) {
return (node * 2 <= heap_size) ? node * 2 : -1;
}

private static int rightChild(int node) {
return (node * 2 + 1 <= heap_size) ? node * 2 + 1 : -1;
}

private static void constructHeap() {
for (int i = heap_size / 2; i > 0; --i) {
max_heapify(i);
}
}

private static void max_heapify(int node) {
int consider;
if (leftChild(node) == rightChild(node)) {  //Missing nodes (both return -1)
return;
} else if (leftChild(node) == -1) {         //left node missing, consider the right one
consider = rightChild(node);
} else if (rightChild(node) == -1) {        //right node missing, consider the left one
consider = leftChild(node);
} else {                                    //both nodes present, evalute which one to consider
consider = array[leftChild(node)] >= array[rightChild(node)] ? leftChild(node) : rightChild(node);
}

if (array[node] < array[consider]) {
int temp = array[node];
array[node] = array[consider];
array[consider] = temp;
max_heapify(consider);
}
}

private static int extractMax() {
if (heap_size == 0) {
System.err.println("Error: Heap is empty!");
return -1;
}
int maxValue = array[1];
int temp = array[1];
array[1] = array[heap_size];
array[heap_size] = temp;
heap_size--;
return maxValue;
}

public static void heapSort(int[] array_input) {

//array to sort
array = array_input;
/*
max_heap size = array.length-1 (-1 because of the 0th index that we are NOT going to consider)
The user should not have to care about leaving the 0th index empty.
But we can't use index 0 due to the rightChild() and leftChild() calculations for
indexes.
*/
heap_size = array.length - 1;
constructHeap();

for (int i = array.length - 1; i > 0; --i) {
array[i] = extractMax();
max_heapify(1);
}
}

public static void main(String[] args) {
int[] array = {0, 7, 5, 99, 3, 2, 1, 22, 33, 42, 1, 332, 1};
heapSort(array);
for (int i = 1; i < array.length; ++i) {
System.out.print(array[i] + " ");
}
}
}


What would be the correct way to heap sort in this case?

Change the methods computing indexes:

private static int leftChild(int node) {
return (node * 2 + 1 <= heap_size) ? node * 2 + 1: -1;
}

private static int rightChild(int node) {
return (node * 2 + 2 <= heap_size) ? node * 2 + 2 : -1;
}


That's all what's needed.

Changing one invalid index (too big) into another one (-1) feels rather hacky. Not doing this and using

private static boolean isValid(int node) {
return node < heap_size;
}


would be better.

I hate static variables and you should too. Replace

private static int[] array;
private static int heap_size;


by arguments. Actually, drop heap_size, as array.length does the job. If you don't want to pass it around, create an object HeapSort. Internally, you would do

new HeapSort(array).sort();


but you can make the constuctor private and expose a static method instead.

• node*2 - 1 returns -1 for node = 0. That's an error. We need to return (node*2+1) for left child and (node*2+2) for the right child. Sep 16, 2014 at 19:46
• @CodeWriter Thanks, fixed. That's what happens when not thinking (I wrote something like this a week ago and now I was using my leaking memory only). Sep 16, 2014 at 19:55