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.