HeapSort Efficiency

Question

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] + " ");
        }
    }
}

Answer 1

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.