2
\$\begingroup\$

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;

}
\$\endgroup\$
1
  • \$\begingroup\$ 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) \$\endgroup\$ – Daniel Monteiro Jul 11 '15 at 2:34
3
\$\begingroup\$

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);
\$\endgroup\$
0

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.