876. Taking the Top Off a Heap

You are given a valid MIN-heap of n values in level order. Remove the minimum by the standard procedure, then print the minimum on one line and the remaining n - 1 values, in level order, on the next.

The standard procedure is:

answer = a[0] move the LAST value into index 0 and shrink the array by one i = 0 loop: pick the smaller of the two children of i; on a TIE pick the LEFT one if there is no child, or that child is not strictly smaller, stop swap with it and set i to that child's index

heap 1 3 2 7 8 5 4 -> 1 then 2 3 4 7 8 5 heap 2 5 4 9 6 7 -> 2 then 4 5 7 9 6 heap 42 -> 42 then empty

Trace the first one. The answer is 1. The last value, 4, moves to index 0, giving 4 3 2 7 8 5. Its children are index 1 (3) and index 2 (2); the smaller is 2, and 2 < 4, so they swap: 2 3 4 7 8 5, and i becomes 2. Index 2 now holds 4 and has child index 5 (5); 5 < 4 is false, so the walk stops.

When the heap held only one value there is nothing left, and the second line is the word empty.

## What most people try first

Removing index 0 and shifting everything left. That produces an array which is usually not a heap at all, because shifting changes every parent-child pairing. It is also O(n).

Promoting the smaller child into the gap, repeatedly. This one is subtle and wrong: it moves the hole down, and when the hole finally lands on a non-leaf position the array has a gap in the middle. A heap must stay a COMPLETE tree, with no holes before the last index, or the index arithmetic stops describing the shape. Moving the last element up first is what keeps the shape complete.

## Why the walk is correct

After the last value lands at the root, every edge below the root is still correct, because nothing below moved. The only suspect edges are the two leaving the root.

Swapping with the SMALLER child repairs both at once. The promoted child was at most its sibling, so it is now at most the sibling as a parent, and it is below its old parent's position, where it is at most the value that used to sit there. The demoted value is now at a position whose subtree was already correct except possibly for its own two edges, which is the same situation one level down. Repeating it until the edges hold takes at most floor(log2 n) steps.

Swapping with the LARGER child instead would satisfy one edge and break the other, which is the classic wrong version of this loop.

## The tie rule, and why it has to be stated

When the two children are equal, both choices produce a valid min-heap, but different ARRAYS. Since the array is the output, the rule is fixed here: take the LEFT child on a tie. 5 5 6 5 6 7 7 5 5 6 is in the tests precisely because it has such a tie.

## The boundary that breaks a careless implementation

n = 1. Removing the only value leaves nothing, and there is no "last value to move to the root" because the last value IS the root. Handle it before the loop and print empty.

The other one is the child index test. A node at index i has a left child only when 2i + 1 < n, and a right child only when 2i + 2 < n. Testing only the left and assuming the right exists reads past the end whenever the node has exactly one child, which happens at most once per heap and is the hardest kind of bug to reproduce.

## What is NOT an overflow here

Values reach 10^9 in magnitude and the only arithmetic is on child indices 2i + 1 and 2i + 2, which are at most about 400002. The largest signed 32-bit integer is 2147483647, so nothing here needs a 64-bit type and no two values are ever combined.

## Related problems

Problem 875 is the other half of the same machinery, and every heap in this block is built from the two together.

## Cost

Time O(log n) for the removal, plus O(n) to read and print. Space O(n).

Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000` - The given array is guaranteed to be a valid min-heap.