The other answers cover the stylistic concerns of your code pretty well already. However, there is still one major issue with your code that warrants another (albeit late)answer: it's incorrectly implemented!
The "heapsort" algorithm that you implemented has a run-time complexity of O(N2). Judging from your comment, you probably realized something was wrong too since the run-time sky-rocketed as you tried to sort more items.
Here are the problem areas I see that's causing the abysmal performance:
- You are re-heapifying the entire array on each iteration. This is of course completely wrong and it's the biggest reason why your code is performing so poorly. You're only suppose to heapify the array once, at the beginning when you start the sort.
- Shifting all the elements down by one after removing the smallest. This is an O(N) operation that can be avoided altogether with a redesign.
- Use of a temp array -- this is also unnecessary. Like quicksort, one of heapsort's advantages is that it's capable of sorting in-place without the need to allocate a temporary buffer.
- Heapifying 'leaf' elements needlessly. By definition, leaf elements don't have any child nodes below them so there's nothing to push down. Therefore, it doesn't make sense to heapify pass the last parent element. In other words, you should be going from
root = 0 to
root < (length / 2). Going pass
length / 2 will just result in unnecessary comparisons:
left < length and
right < length will always be false.
It's typical to write 2 helper functions when implementing heapsort:
heapify that turns the array into a heap, and a
filter_down function to enforce the heap property for the element passed in. You usually implement
heapify with the help of the filter function.
Note that the stl has heap functions that does exactly those tasks:
I'll leave the utility functions for you to figure out but here's how the top view of heapsort should look:
void heapsort(int *begin, int *end)
// assume end is one pass the last element. eg. arry + length;
while(begin != --end)
swap(*begin, *end); // invariant: the next item to order will be at the top
// after the swap, the next biggest/smallest item may not be
// at the top. use push_down to fix this and preserve the heap property.
Note that you do not call heapify inside the loop. After the swap, only the top element might violate the heap property -- the rest of the remaining elements are still in a heap. To fix the top you just need to
push_down that element until it reaches the right level. This can be done in O(log n) since that's how deep the tree can ever be.
Edit: Added more explanation and example.
An analogy might help clear up the idea behind heapsort. You can think of heapsort as hosting an elimination tournament where in each match-up bracket 3 contenders duke it out. The winner will move up the bracket to the next match-up and the 2 losers stay where they are. The tournament starts out by doing all the match-ups at the bottom bracket first, progressively moving up -- this is basically the heapifying phrase.
After you heapify, that's finishing one entire tournament -- the champion is at array and the runner-ups will be either array or array. To find the runner-up you host another match-up between them plus a 3rd contender from the bottom bracket.
Now if you think of 'push_down' as a sort of scorekeeper, his job is to keep track of the winners and move them up the bracket + what match-ups need to take place. Each match-up has 1 'defender'(the guy one bracket up) and 2 'challengers'. If the defender loses, he swaps places with the challenger that defeated him. If there are more challengers below the defender's new spot, another match-up is between them. The defender will get pushed further and further down the match-up bracket until he can successfully defend his spot or there are no more opponents to defend against.
The 'push_down' function is probably the most important helper since that's where the reordering actually happens. It's almost analogous to partition in qsort or merge in mergesort.
Here's basically what the push_down function would look like: (note, it's not thoroughly tested)
void push_down(int *begin, int *end, size_t defender = 0)
// at the very bottom?
if(defender >= std::distance(begin, end) / 2) return;
size_t challenger = defender * 2 + 1;
// is there a right-child?
// Note that in even# arrays, last parent doesn't have a right child
if(begin + challenger + 1 != end)
if(begin[challenger + 1] < begin[challenger])
// defended successfully?
if( !(begin[challenger] < begin[defender]) ) return;
// challenger wins
push_down(begin, end, challenger);
Note that the array will be sorted in descending order if smallest is at the top. But this is trivial to fix once sorting is working -- just flip the comparison being done.
You should heed the advice from the other answers and extract out those functions. It will make your code easier to reason about.