875. Pushing One Value Into a Heap
You are given a valid MIN-heap of n values in level order, and one more
value x. Insert x by the standard procedure and print the resulting array
of n + 1 values, in level order.
The standard procedure is:
place x at the end of the array
while the value is not at the root AND its parent is STRICTLY greater:
swap it with its parent
heap 2 5 4 9 6 7, x = 3 -> 2 5 3 9 6 7 4
heap 2 5 4 9 6 7, x = 8 -> 2 5 4 9 6 7 8
heap 1 2 3 4 5 6 7, x = 0 -> 0 1 3 2 5 6 7 4
Trace the first one. 3 goes to index 6. Its parent is index
(6 - 1) / 2 = 2, holding 4, and 4 > 3, so they swap: the array becomes
2 5 3 9 6 7 4 and the 3 is now at index 2. Its parent is index 0 holding 2,
and 2 > 3 is false, so the walk stops.
The second row never moves: 8 lands at index 6, its parent holds 4, and
4 > 8 is false immediately.
## What most people try first
Rebuilding. Append x, then re-heapify the whole array, or sort it. Sorting
gives a valid min-heap, but not THIS array, and the question asks for the array
the insertion procedure produces. Re-heapifying is O(n) where the insertion
is O(log n), and on a heap of 200000 values that is the difference between
200000 operations and 17.
## Why the walk is correct
Before the insertion every parent-child edge satisfies the rule. Appending
x can only break ONE edge: the one joining x to its parent. Every other
edge is untouched.
Swapping x with a parent p where p > x fixes that edge, and it cannot
break anything else. The sibling of x was at least p, and x is now
below p, so x is at most both of its new children. And p has moved down
to where x was, which is below a value that was already at most p. So the
only possibly broken edge is again the one above the moving value, one level
higher. The walk therefore repeats the same single repair, at most
floor(log2(n + 1)) times, and stops when the edge holds.
## The comparison that decides the equal case
The loop stops when the parent is NOT strictly greater, so an equal parent
stops the walk. Change > to >= and equal values keep swapping past each
other: on 4 4 4 4 4 with x = 4 the strict version leaves the array
unchanged while the loose version bubbles the new 4 all the way to the root.
Both arrays are valid min-heaps, so no validity check catches the difference.
Here the rule is STRICT.
## The off-by-one that breaks a careless implementation
The parent of index i is (i - 1) / 2 with integer division, not i / 2.
The second form is right for a 1-based heap and wrong for a 0-based one: at
i = 1 it gives 0 by luck, and at i = 2 it gives 1 instead of 0, so the
new value climbs the wrong branch. Stop the loop at i == 0, since index 0
has no parent and (0 - 1) / 2 is either -1 or a very large unsigned number.
## What is NOT an overflow here
Values reach 10^9 in magnitude and the only arithmetic is the parent index
(i - 1) / 2, where i is at most 200000. The largest signed 32-bit
integer is 2147483647, so nothing here needs widening. No two values are
ever added, so there is no sum that could overflow.
## Cost
Time O(log n) for the insertion itself, plus O(n) to read and print.
Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i], x ≤ 1000000000` - The given array is guaranteed to be a valid min-heap.
Input
The first line contains one integer n.
The second line contains n integers, a valid min-heap in level order.
The third line contains the integer x to insert.
Output
Print the n + 1 values of the resulting array in level order, on one line, separated by single spaces. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.