Confused by my heap sort and why it isn’t working via /r/learnprogramming

Confused by my heap sort and why it isn’t working

All the relevant code:

private static void heapSort(int[] array) { int[] heapArray = new int[array.length+1]; for(int i = 0; i < array.length; i++) { heapArray[i+1] = array[i]; } int heapSize = heapArray.length-1; buildMaxHeap(heapArray, heapSize); print(heapArray); //building the heap part is right while(heapSize > 1) { swap(heapArray, 1, heapSize); print(heapArray); heapSize--; maxHeapify(heapArray, 1, heapSize); print(heapArray); } print(heapArray); } private static void buildMaxHeap(int[] heapArray, int heapSize) { for(int index = heapSize/2; index > 0; index--) { maxHeapify(heapArray, index, heapSize); } } private static void maxHeapify(int[] heapArray, int index, int heapSize) { int leftChild = 2*index; int rightChild = 2*index+1; int largest = index; if(leftChild <= heapSize && heapArray[leftChild] > heapArray[index]) { largest = leftChild; } if(leftChild <= heapSize && heapArray[rightChild] > heapArray[largest]) { largest = rightChild; } if(largest != index) { swap(heapArray, index, largest); maxHeapify(heapArray, largest, heapSize); } } private static void print(int[] array) { System.out.println(Arrays.toString(array)); } private static void swap(int[] array, int a, int b) { //helper method that swaps two elements in an array int temp = array[a]; array[a] = array[b]; array[b] = temp; } 

Building my max heap from an array works. All my code up until line 14 works. I used an input 5, 6, 4, 2, 1 to test.

At the print statement at line 9, it printed 0, 6, 5, 4, 2, 1 which is correct

At the print statement in line 13, it printed 0, 1, 5, 4, 2, 6 which is also correct (I'm not extracting max, just putting the max root to the end then changing the size of the heap so it's like I'm deleting it from the heap)

But then at the print statement at 16 for some reason it prints 0, 5, 6, 4, 2, 1 – have on idea whatsoever why this happened. My maxHeapify method does work because it can build the max heap originally so I'm not sure what's going on.

Some notes that explain why certain parts of my code are the way they are:

I made a new copy array heapArray so I could do parent*2 = left, parent*2 + 1 = right. Indexes are now associated with the position in the heap (index 1 at root, index 2 is left child of root, etc). Otherwise I'd just add 1 which is fine too.

I changed my code from what I read in CLRS to accommodate the heapSize decreasing as I move the max root to the end.

Overall, the problem is between lines 13 and 16 because the print statement before it works fine but the one at 16 doesn't.


Submitted July 14, 2017 at 08:02PM by eatingpoopinrobarts
via reddit


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s