Heapsort?

[hopesfall]

Can anyone briefly describe the heapsort algorithm to me? How is the algorithm able to work "in place", i.e., without making use of any additional storage space?

My book tries to explain this but I don't seem to understand...

[Kyon]

In order, watch these:
http://www.youtube.com/watch?v=v1YUApMYXO4
http://www.youtube.com/watch?v=6NB0GHY11Iw

[hamsterman]

Do you understand what a heap is and how it can be represented by an array?

The idea of heapsort is that in a heap, it is easy to find the greatest element (it's on top). It's also quite easy to form a heap from a set of numbers. It's really just much more intelligent version of selection sort.

What is the problem with being "in place"? Many algorithms are in-place. For example bubble sort is. A naive version of quicksort isn't, as you'd create arrays "less than pivot" and "more than pivot". Quicksort can be made in-place too though. Of course all algorithms use some extra space for variables. That space is negligible when sorting a large array though.

[Kyon]

I believe, by additional storage space, he means additional "array spaces" or arrays. The videos I gave you work fine on showing the "in place" part: you only have to keep track of the number of elements sorted so far.