Heap: Delete-max (sift-down)

Heap: delete-max with sift-down (heapsort)

First build a max-heap from the integers in input order (insert is provided), then repeatedly delete the maximum, printing each extracted maximum until the heap is empty. Because every step removes the current maximum, the output comes out in descending order — this is heapsort.

Complete delMax (sift-down): take h[0] as the return value, move the last element to the root and decrement *n, then sift down from index 0 — pick the larger of the left and right children; if it is larger than the current node, swap and continue, stopping when the node is larger than both children or has none.

Pitfall: sift-down must compare against the larger of the two children; comparing only with the left child breaks the heap. After moving the last element to the root you must do (*n)--, otherwise the old last element becomes a ghost that gets extracted again.

Input

• Line 1: integer n (may be 0).
• Line 2: n integers, inserted in this order to build the heap.

Output

• One line: the values from repeated delete-max (i.e. descending), a space after each value.

Example: input 7 / 50 30 70 20 40 60 80 -> 80 70 60 50 40 30 20 .