Hey guys,

I'm trying to create a iterative heapsort program and for some reason when I input 10 random numbers into the array, only 9 numbers are sorted. Here is an example of my input/output:

Input:
45 15 2 44 30 83 30 86 66 49 // 10 random numbers
Output:
2 15 30 30 44 49 66 83 86 // only 9 comes back sorted, the first index value before it was sorted is missing. In this case, 45 is missing.

Here is my code:

import java.util.Random;
public class Heapsort {

  private static int indexOfMax(int []a, int i, int j) {
    if (a[i] >  a[j])
      return i;
    else
      return j;
  }

  private static void checkKids(int[] a,  int i, int  endOfHeap) {
    if (i > endOfHeap)
      return;

    int left = (2 * i ) <=  endOfHeap? 2 * i: 0;
    int right = (2 * i + 1) <= endOfHeap? 2 * i + 1: 0;

    int larger = indexOfMax(a, i, indexOfMax(a, left, right));
    if (larger != i) {
      swap(a, i, larger);
      checkKids(a, larger, endOfHeap);
    }

  }

  private static void checkParent(int[] a, int i) {

    if (i > 1) {
      if (a[i/2] < a[i]) {
    swap(a, i/2, i);
    checkParent(a, i/2);
      }
    }
  }

  private static void build(int[] a ) {

    for (int i= 2; i < a.length; i++) {
      checkParent(a, i);
    }
  }



  private static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

  private static void printArray(int[] a) {

    for (int i=1; i <a.length; i++)
      System.out.print(a[i]+" ");

    System.out.println();
  } 

  private static void sort(int [] a) {
    a[0] = Integer.MIN_VALUE;

    Heapsort.build(a);

    for(int endOfHeap = a.length-1; endOfHeap> 1;) {
      swap(a, 1, endOfHeap);
      endOfHeap--;
      checkKids(a, 1, endOfHeap);
    }
  }

  public static void main (String[] args) {
   int n = 0;
   if(args.length == 1){
        try{
           n = Integer.parseInt(args[0]);
            }catch(NumberFormatException e){
                System.err.println("Invalid input.");
                System.exit(1);
            }
        }
        int a[] = new int[n];
        Random generator = new Random();
        for(int i = 0; i < a.length; i++){
            a[i] = generator.nextInt(100) + 1;
            System.out.print(a[i] + " ");
        }
        System.out.println();
    Heapsort.sort(a);
    printArray(a);
  }

}

Any help would be appriciated. Thanks.

Have you tried debugging the code by adding some println statements to show you what the code is doing?

Try using the Arrays class's toString() method to format the array for printing:
S.o.p("before=" + Arrays.toString(a)); // show before sort

Edited 4 Years Ago by NormR1

If you look closely, there are a couple things in your code that are off.

1) Start from looking at line 60, what are you doing there? What is the consequence of doing that?
2) Look at how you use the loop to display your array value at line 53. What range would it display?
3) You may need to consult your algorithm again. The problem seems to be from the array size and how you manipulate with it. My guess is that you initialization for your array is off.

Edited 4 Years Ago by Taywin

This article has been dead for over six months. Start a new discussion instead.