Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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];
    }
}
share|improve this question
2  
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. –  Josay Mar 1 at 21:08
    
This code appears to work for me (array sizes from 10 to 10,000) ... why do you think it is broken? –  rolfl Mar 1 at 21:29
    
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). –  user37872 Mar 1 at 21:32
    
In the future, be as specific as possible when describing the problem. An "error" isn't too helpful while StackOverflowException gives a big clue. –  David Harkness Mar 1 at 21:54

1 Answer 1

up vote 5 down vote accepted

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];
  }
}
share|improve this answer
    
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. –  user37872 Mar 1 at 21:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.