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

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