1
\$\begingroup\$

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] + " ");
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – CodeWriter Sep 16 '14 at 19:46
  • \$\begingroup\$ @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). \$\endgroup\$ – maaartinus Sep 16 '14 at 19:55

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.