### Heap Sort Infinite Loop

I am trying to understand what is going wrong with my heap sort. It compiles, populates the vector, prints it and gets to this one particular method call and I can't seem to track the issue for the life of me. I implemented Wikipedias psudo-code to try to get it to work but I just can't figure it out. Hopefully you all can help me spot why its taking x>10 minutes and still not finishing. Its probably looping somewhere...

// Heap Sort method
 ``1234567891011121314151617181920212223`` ``````void heapSort(vector & sortablevector, size_t count) { make_vector_heap(sortablevector, count); size_t end = count-1; //in languages with zero-based arrays the children are 2*i+1 and 2*i+2 while ( end > 0 ) { //(swap the root(maximum value) of the heap with the last element of the heap) swap( sortablevector[end], sortablevector[0] ); //(decrease the size of the heap by one so that the previous max value will //stay in its proper placement) end = end - 1; //(put the heap back in max-heap order) downHeap( sortablevector, 0, end ); } }``````

// My version of wikipedia's 'Heapify' method
 ``12345678910111213141516`` ``````void make_vector_heap(vector & sortablevector, size_t count) { size_t start = ( count - 1) / 2; while ( start >= 0 ) { //(sift down the node at index start to the proper place such that all nodes below //the start index are in heap order) downHeap(sortablevector, start, count-1 ); start = start - 1; } }``````

//my version of wikipedias 'siftdown' method
 ``1234567891011121314151617181920212223242526272829303132333435`` ``````void downHeap(vector & v, size_t start, size_t end) { size_t root = start; while ( ( root * 2 ) + 1 <= end ) { size_t child = ( root * 2 ) + 1; size_t numswap = root; if ( v[numswap] < v[child] ) { numswap = child; } if ( ( child + 1 <= end ) && ( v[numswap] < v[child + 1 ] ) ) { numswap = child + 1; } if (numswap != root) { swap( v[root], v[numswap] ); root = numswap; }else{ break; } } }``````

Hopefully this makes sense? Any help is appriciated! Thanks :)
Last edited on
Maybe someone will actually see this now. Help would be greatly appriciated. Thanks.
Last edited on
By far the quickest & easiest way to solve run time problems is to use a debugger. Should be easy if you are using an IDE. Step through the code 1 line at a time, keep an eye on the value of your variables to deduce where it all goes wrong.

Found this code with a google search ( heap sort C++ example )- don't know how good it is. Some of the others returned by google weren't very goodIMO.

 http://crackprogramming.blogspot.com.au/2012/11/heap-sort-c-implementation.html

Maybe you can compare to your code.

Cheers

Edit: A really minor thing :

This :

`start = start - 1;`

can be written :

 ``123`` ``````start--; // decrementing start++; // incrementing ``````

if not decrementing by 1, then use:

 ``12`` ``````start -= 2; // start = start -2 start += 2 // start = start + 2 ``````

There are other assignment operators as well.
Last edited on
Topic archived. No new replies allowed.