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

• Daniel Monteiro: Looks like what I would do, if only somewhat pirate-like 'arr'! =-P Also tested and handles well empty and single-element-arrays. (BTW, tested in Android, since I had Android Studio open at the time)

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