Search code examples
sortingheapsort

Ascending and Descending Heapsort

Which heap is to be built for ascending sorting and descending sorting. Please explain whether any heap (max or min) could be used for any sorting (ascending or descending).

Solution

  • Normally you will use a max-heap for ascending sorting and a min-heap for descending sorting.

    This has to do with the way the heap sort algorithm is normally described:

    1. Build a max-heap with the original data
    2. Now the maximal element is at the root of the tree, take this element at switch it with the last element of the tree.
    3. Look at the new tree, that you get by ignoring the last position (this is already sorted). The new tree might not be a max-heap any more, so we transform it into one by sifting the root down.
    4. Go to step 2 and repeat until tree is empty.

    You can see the algorithm in work in the following graphic: (Created by Gms)

    Heap-Sort example

    As you can see in each step we put the maximum (first the biggest number, then the second biggest number, ...) at the end of the array and they end up ascendantly sorted.

    But obviously you can also use a max-heap to generate a descending sorting. Simply put the found maxima into a new array. (Or simply invert the sorted array at the end.)