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