# Sorting an integer array using heap sort

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;

}

• 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) – Daniel Monteiro Jul 11 '15 at 2:34

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


Here is how you would use the HeapSort class and it's sort method:
HeapSort.sort(myIntArray);