Heap: Insert (sift-up)

Heap: Insert with sift-up (build a max-heap)

Read the integers and insert them in input order into a max-heap using insert + sift-up, then print the whole heap in array order (index 0,1,2,…).

The max-heap is stored in an array h[] (0-indexed): the parent of i is (i-1)/2, children are 2i+1 / 2i+2. Complete insert: put the new value at the end of the array, then repeatedly compare with its parent — swap upward while it is larger than its parent, stopping when it is <= the parent or reaches the root index 0.

Pitfall: the sift-up stop condition is h[i] <= h[parent] OR i == 0. Forgetting i==0 keeps computing a parent index past the root; writing < instead of <= causes useless swaps when there are duplicate values.

Input

• Line 1: integer n (may be 0).
• Line 2: n space-separated integers, inserted in this order.

Output

• One line: the final heap array, a space after each value.

Example: input 7 / 50 30 70 20 40 60 80 -> 80 40 70 20 30 50 60 (80 sifts up to become the root).