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.

## Advertisement

## 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.