I'm trying to write an array based implementation of the heap sort algorithm. The goal is to build a heap in an array and then remove the minimum element at the root of the array and put it back into the original array. This is done until the array is sorted.
The replacement for the root is supposed to come from the last element in the array, which is then removed and put in the root. The new root element is swapped with one its children if necessary. This continues until it is in the correct location
However I keep getting array index out of bounds exception and I just cannot find the problem. I've been working on this for way too long.
I would really appreciate it if someone could help me.
public class ImprovedHeapSort<T>
{
/**
* @param unsortedArr Array to be sorted
* @return sortedArr The sorted array
*
* Static method which is an improved version of the HeapSort algorithm. The array
* is used to create a sorted array, which is treated as a minheap.
*
* The root is at index 0 and the last element is at index length-1.
* Each element is compared to its children, which are at positions 2n+1 and 2(n+1).
* Swapping and comparison continues until the root is reached.
*
*
*/
public static <T extends Comparable<T>> T[] HeapSort (T[] unsortedArr)
{
/*
* Throw exception if array is empty.
*/
if (unsortedArr[0] == null)
{
throw new EmptyCollectionException("Array");
}
/*
* If array only contains one element.
*/
if (unsortedArr.length == 1)
{
return unsortedArr;
}
T[] heapArr = Arrays.copyOf(unsortedArr, unsortedArr.length);
for(int i = 0; i < unsortedArr.length; i++)
{
heapArr[i] = unsortedArr[i];
/*
* Swapping to put element in appropriate location, if necessary.
*/
int cur = i;
T temp = heapArr[i];
/*
* Swapping until root isn't reached and the element being added
* would no longer be less than its parent.
*/
while(cur > 0 && temp.compareTo(heapArr[(cur-1)/2]) < 0)
{
heapArr[cur] = heapArr[(cur-1)/2]; //Swap cur with parent
cur = (cur-1)/2; //Move up to parent
}
heapArr[cur] = temp; //Insert at appropriate spot.
}
/*
* Remove the root element from the heap array and add it to unsortedArr
*
*/
for (int y = 0; y < unsortedArr.length; y++)
{
int count = heapArr.length - (y+1); //Count decreased after every pass.
T rootElem = heapArr[0]; //Store root
heapArr[0] = heapArr[heapArr.length- (y+1)]; //Set root to last element.
unsortedArr[y] = rootElem; //Add root to unsortedArr
int node = 0;
int left = 1;
int right = 2;
int next;
if ((heapArr[left] == null) && (heapArr[right] == null))
next = count-1;
else if (heapArr[right] == null)
next = left;
else if (heapArr[left].compareTo(heapArr[right]) < 0)
next = left;
else
next = right;
T temp = heapArr[node];
/*
* Swap until appropriate location is found. Least child is shifted up.
*/
while ((next < count) &&
(heapArr[next]).compareTo(temp) < 0)
{
heapArr[node] = heapArr[next];
node = next;
left = 2 * node + 1;
right = 2 * (node + 1);
if ((heapArr[left] == null) && (heapArr[right] == null))
next = count-2;
else if (heapArr[right] == null)
next = left;
else if (heapArr[left].compareTo(heapArr[right]) < 0)
next = left;
else
next = right;
}
heapArr[node] = temp; //Insert node at appropriate location
}
return unsortedArr;
You have a few bounds errors in your code.
First, let's look here:
/*
* Throw exception if array is empty.
*/
if (unsortedArr[0] == null)
{
throw new EmptyCollectionException("Array");
}
This code won't actually throw an exception if the array is empty. Instead, it tries to look at index 0, see if that value is null, and, if so, throw an exception. Therefore, if you try to pass in an array of size 0 or an empty array, you'll get either a bounds error or a null pointer exception. To fix this, try rewriting it as
if (unsortedArr == null) {
...
}
You probably don't want to automatically fail on an array of length 0. It's perfectly well-defined how to sort it: it's already sorted!
Additionally, I'm not sure what you meant to do here, but I'm almost positive this isn't what you intended:
int node = 0;
int left = 1;
int right = 2;
int next;
if ((heapArr[left] == null) && (heapArr[right] == null))
next = count-1;
else if (heapArr[right] == null)
next = left;
else if (heapArr[left].compareTo(heapArr[right]) < 0)
next = left;
else
next = right;
Notice that node, left, and right are always indices 0, 1, and 2, regardless of how big the array is. If you pass in a small array (say, size 2), this will read off the end.
Going forward, the sense I get is that you need to learn how to debug your programs a bit more. The exceptions raised here when I ran the code took me right to the line of the program that caused the problem, and from there it wasn't too hard to figure out where something unusual was going on. I hope this helps point you in the right direction, and good luck!