descending heap sort

Question

use heap sort to sort this in descending order and show the steps or explanation please below is the tree

                             79
                       33           57
                    8     25    48

below is the array 79 - 33 - 57 - 8 - 25 - 48 ok ascending is easy because the largest element is at the top we can exchange the last element and the first element and then use heapify as the sample code in wikipedia describes it.

ok let me clarify, the heap is built on the tree that I drew. I know the steps to do ascending order and the array would look like 8 - 25 - 33 - 48 - 57 - 79. but what are the steps to do descending. This is a very straight forward question. just explain the steps needed to order the array in descending order.

Answer 1

This looks like a max heap, so to sort in descending order is trivial:

FUNCTION descSortedFrom(Heap h) : Array

   LET N := h.size
   LET ret := NEW Array (size = N)

   FOR i = 0..N-1 DO
      ret[i] := h.deleteMax

   RETURN ret

Binary heap, binomial heap, and fibonacci heap all support deleteMax on max heap (or analogously, deleteMin on min heap) in O(log N), so overall this is O(N log N), which is optimal for comparison-based sort.

Note that this uses an external storage array for simplicity. If you insist on using the same array as the heap, then simply do the ascending sort as you've done, then (guess what?) reverse the array in O(N).

---

An alternative solution

This is more complicated than necessary, but is one-pass and in-place. Essentially, instead of treating array elements [0..k) as your heap elements, you take [N-k..N) instead. You must modify heapify to take a starting offset to accommodate this change.

To illustrate, as you've figured out, this is how you sort in ascending order:

entire array = [ the heap elements ; the sorted asc elements ]

Essentially you build the sorted asc elements right to left, swapping the first of the heap (its max) with the last element of the heap, shrinking the heap size by one, and then heapifying the remaining heap elements.

To sort in descending order is conceptually the same:

entire array = [ the sorted desc elements ; the heap elements ]

You build the sorted desc elements left to right. The max of the heap does not need to be relocated, you simply shrink the heap size by one, but instead of cutting off at the tail, you cut off at the head. You must therefore give an offset argument to heapify so it knows where the heap elements actually start in the array.