Implementation of HeapSort

Question

The following code is an implementation of heapsort on an array

public static void heapSort(int[] inputArray){
 /* Creates an array A which will contain the heap */
 /* A has size n+1 to allow 1-based indexing */
 int n = inputArray.length;
 int[] A = new int[n+1];
 int temp = 0;
 /* Copies the array inputArray into A, with inputArray[i] being stored in A[i+1] */
 for(int i=0; i<n; i++){
 A[i+1] = inputArray[i];
 }
 constructHeap(A, n, 1);
 removeMax(A, n);
 copyBack(A, inputArray);
}
 /* Transforms A into a max-heap using a 'bottom-up' algorithm. */
public static void constructHeap(int[] A, int n, int i){
 if(2*i>n) return;
 constructHeap(A, n, 2*i);
 constructHeap(A, n, 2*i+1);
 bubbleDown(A, n, i);
}
/*recursively swaps parent/child relationships until the max-heap property is satisfied. */
public static void bubbleDown(int[] A, int n, int i){
 if(2*i>n) return;
 int leftChild = 2*i;
 int rightChild = 2*i+1;
 int max = leftChild;
 if(rightChild<=n && A[max]<A[rightChild]){
 max = rightChild;
 }
 if(A[i]<A[max]){
 int temp = A[i];
 A[i] = A[max];
 A[max] = temp;
 bubbleDown(A, n, max);
 }
}
 /* Performs a sequence of n 'remove-maximum' operations, storing the removed element at
 each step in successively smaller indices of A */
public static void removeMax(int[] A, int i){
 for(int i=n; i>0; i--){
 int temp = A[1];
 A[1] = A[i];
 bubbleDown(A, i, 1);
 A[i] = temp;
}
 /* Copies the sorted values in A back into inputArray, with inputArray[i] getting
 the value from A[i+1] */
public static void copyBack(int[] A, int[] inputArray){
 for(int i=0; i<inputArray.length; i++){
 inputArray[i] = A[i+1];
 }
}

• SylvainD: Welcome to CodeReview.SE ! You are suppose to provide some actual working code to review. In your case, it seems to be pretty close to working so it would be really helpful if you could tell us more about your issue.
• user37872: Well as I began writing the code, I was working with a small array of size 10 containing elements in the range of [1, 100], and worked out the bugs until it worked. Then I subsequently tested the code on larger input files. When the input array has 999 values, it sorts just fine, but when I try with 100,000 values, I get an error at line 95, which is the recursive call to removeMax(A, i-1).
• David Harkness: In the future, be as specific as possible when describing the problem. An "error" isn't too helpful while StackOverflowException gives a big clue.

Answer 1

Your constructHeap method works in O(n), and you call in O(n) times from removeMax method, so your code works in O(n^2), so it is not a correct implementation of Heapsort.

Comments:

public static void heapSort(int[] inputArray) {

Why do you need another array? Heapsort is in-place.

 /* Creates an array A which will contain the heap */

Why do you need 1-based indexing? You don't seem to use it anywhere, and 0-based is more convenient.

 /* A has size n+1 to allow 1-based indexing */
 int n = inputArray.length;
 int[] A = new int[n + 1];

You don't use this variable.

 int temp = 0;
 /* Copies the array inputArray into A, with inputArray[i] being stored in A[i+1] */

You should replace this loop with System.arraycopy(...) call

 for (int i = 0; i < n; i++) {
 A[i + 1] = inputArray[i];
 }
 constructHeap(A, n, 1);
 removeMax(A, n);
 copyBack(A, inputArray);
}

Consider transforming such comments into valid javadoc.

/* Transforms A into a max-heap using a 'bottom-up' algorithm. */
public static void constructHeap(int[] A, int n, int i) {
 if (2 * i > n) {
 return;
 }
 constructHeap(A, n, 2 * i);
 constructHeap(A, n, 2 * i + 1);
 bubbleDown(A, n, i);
}

Comment?

public static void bubbleDown(int[] A, int n, int i) {
 if (2 * i > n) {
 return;
 }
 int leftChild = 2 * i;
 int rightChild = 2 * i + 1;
 int max = leftChild;
 if (rightChild <= n && A[max] < A[rightChild]) {
 max = rightChild;
 }
 if (A[i] < A[max]) {
 int temp = A[i];
 A[i] = A[max];
 A[max] = temp;
 bubbleDown(A, n, max);
 }
}
 /* Performs a sequence of n 'remove-maximum' operations, storing the removed element at
 each step in successively smaller indices of A */
public static void removeMax(int[] A, int i) {
 if (i == 0) {
 return;
 }
 int temp = A[1];
 A[1] = A[i];
 constructHeap(A, i, 1);
 A[i] = temp;

So you make O(n) recursive calls? This is causing StackOverflowException with large n and harming your running time. Consider transforming this tail recursion into a loop.

 removeMax(A, i - 1);
}
 /* Copies the sorted values in A back into inputArray, with inputArray[i] getting
 the value from A[i+1] */
public static void copyBack(int[] A, int[] inputArray) {

ditto

 for (int i = 0; i < inputArray.length; i++) {
 inputArray[i] = A[i + 1];
 }
}

• user37872: Thanks for the help. I had meant to use bubbleDown() inside removeMax() instead of constructHeap(), so now that I've replaced that, the running time has gone to O(nlogn). Replacing the recursion with a loop did the trick with StackOverflowException as well. Thanks again.