Sorting an integer array using heap sort

Question

I have written this program to sort an array using heap sort. Please review it for further improvements.

public static void main(String[] args) {

    int arr[] = {14, 70, 51, 16};

    System.out.println("Input Array : " + Arrays.toString(arr));

    buildMaxHeap(arr, arr.length);

    System.out.println("Max Heap Order : " + Arrays.toString(arr));

    heapSort(arr);

    System.out.println("Sorted Array : " + Arrays.toString(arr));
}

private static void buildMaxHeap(int[] arr, int len) {
    // any nodes after n/2 are leaves node and could be without children
    for (int i = (len) / 2; i >= 0; i--) {
        // bubble up to build max heap
        bubbleUp(arr, i, len - 1);
    }
}

private static void heapSort(int[] arr) {
    // now run the sort process
    for (int j = arr.length - 1; j >= 0;) {
        // bubble up the nodes so that tree can satisfy the max heap
        // property
        // i.e any Node B <= to its Parent Node A.
        // This swap method will shift lower to down and higher to up.
        swap(arr, j, 0);
        // decrement the size of heap so that previous max value stays in
        // place
        j = j - 1;
        // now bubble up again from 0 to (heap -1) j
        // means put the heap back.
        bubbleUp(arr, 0, j);
        System.out.println("Sorted Array : " + Arrays.toString(arr));
    }
}

private static void bubbleUp(int[] arr, int start, int end) {
    // set the root to start
    int root = start;
    while ((root * 2) + 1 <= end) { // root should have atleast one child
        int child = (root * 2 + 1); // point to left child

        // if child has siblings and left child is less than sibling
        if (child + 1 <= end && arr[child] <= arr[child + 1]) {
            child = child + 1; // make this child right child
        }

        // if root is less than child (could be left | right) then bubble up
        if (arr[root] < arr[child]) {
            // swap the node with max value child node
            swap(arr, root, child);
            // set the root to the child level, so that subtrees if any
            // could be shift
            root = child;
        } else {
            root++; // make it bigger to exit out the loop
            // return; // return if root node is greator than child node.
        }

    }

}

private static void swap(int[] arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;

}

Answer 1

Why do you need to pass the length of an array to buildMaxHeap?

private static void buildMaxHeap(int[] arr, int len) {

The functions itself can just use find the length property itself because it is getting the actual array from function parameters.

However, I still believe that it was smart idea to check that i was less than len, which was the length of the array rather than just checking if i was less than the length the array because it is unnecessarily efficient to constantly access the length property of an array.

Here is what I mean:

private static void buildMaxHeap(int[] arr) {
    // any nodes after n/2 are leaves node and could be without children
    int len = arr.length;
    for (int i = (len) / 2; i >= 0; i--) {
        // bubble up to build max heap
        bubbleUp(arr, i, len - 1);
    }
}

---

All of your functions (except main) are very cluttered up with comments. I recommend that you add JavaDoc to all these functions and include as much explanation as you need up there.

That way, if there any confusions about something in a function, the answer can be found above the function, rather than in the function.

---

This line of heapSort

System.out.println("Sorted Array : " + Arrays.toString(arr));

is confusing in two ways:

1. You are printing the same message in main so I don't see why you are doing it again here.

2. This method is for "heap-sorting" an array, not for sending output to the user. If possible, all input and output should be done inside main.

---

Note: This may not apply, but you didn't include the class definition so I do not know.

I recommend calling this class HeapSort, and then having a single static public method called sort that takes a single array and "heap-sorts" it.

That way, if you are writing other code that needs to "heap-sort" an array, you can use the HeapSort class and call it's sort method to sort it. This will make your code more organized.

Here is what I mean:

public class HeapSort {
    public static void sort(int[] arr) {
        [heapSort code]
    }

    ... your other private methods...
}

Now your code is more organized and is ready to be used by another class.

Here is how you would use the HeapSort class and it's sort method:

HeapSort.sort(myIntArray);