What’s wrong with my In Place Heap Sorting code

I’m working on a school assignment and the assignment was to make a heap sorting (In Place) program. Now the program works perfectly fine for arrays with under +- 20 elements, above that it occasionally messes up, however I can’t seem to find what’s wrong.

/**
 * swaps two elements in an array
 *
 * @param a array
 * @param i position of element to swap in a
 * @param j position of element to swap in a
 */
public static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

/**
 * restores the heap property in a heap represented as an array
 * 4 5 0
 * <p>
 * restoreHeap([4, 5, 0], 0, 3)
 * biggest = 1
 *
 * @param heap  array representation of a heap,
 *              which might be invalidated
 * @param root  index of the root of the heap,
 *              which might be a subtree of the overall heap
 * @param range index of the last element in the heap,
 *              array elements with an index > range are not part of the heap
 *              <p>
 *              when the heap property is invalid at root,
 *              the method fixes the heap first locally before fixing the affected subtree
 */
public static void restoreHeap(int[] heap, int root, int range) {
    final int left = root * 2 + 1;
    final int right = root * 2 + 2;
    final int size = root + range;
    int biggest = root;
    if (left < size && heap[left] > heap[biggest]) {
        biggest = left;
    }
    if (right < size && heap[right] > heap[biggest]) {
            biggest = right;
    }

    if (biggest != root) {
        swap(heap, biggest, root);
        restoreHeap(heap, biggest, range - (biggest - root));
    }
}


/**
 * turns an array of integers into a heap
 * <p>
 * this is an in-place algorithm, the heap is built in the array itself
 * 1 2 4 5 9 3
 *
 * @param array of integer numbers,
 *              on return, this array represents a valid heap
 */
public static void buildHeap(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int temp = i;
        while (array[temp / 2] < array[temp]) {
            swap(array, temp / 2, temp);
            temp /= 2;
        }
    }
}

/**
 * sorts an array of integer numbers
 * <p>
 * this is an in-place algorithm, the heap is built in the array itself
 *
 * @param array of elements, on return, this array represents a valid heap
 */
public static void inPlaceHeapSort(int[] array) {
    buildHeap(array);
    int arrSize = array.length;
    while (arrSize > 1) {
        swap(array, arrSize - 1, 0);
        arrSize--;
        restoreHeap(array, 0, arrSize);
    }
}

The skeleton for the methods was already there so if you’re asking why certain parameters are even there, it’s because it was compulsory.

Answer

The problem seem’s to be indexing, the indexing for left and right seems to be wrong

final int left = root * 2 + 1; final int right = root * 2 + 2;

here you should change the code to

final int left = root * 2; final int right = root * 2 + 1;

Also remember that you have to index the array from 1, instead of 0.

Advertisement

Answer