Challenge lab in Heaps and Priority Queues

Mission

Print the median after each inserted integer; use .5 for half values.

Learning outcome: Maintain two heaps for streaming medians

Correctness contract

Invariant: Every parent has priority over its children, and the root is the next item removed.

Required technique: Maintain a max-heap lower half and min-heap upper half with size difference at most one.

Complexity target: time O(n log n); space O(n).

Input and output

Input: n followed by exactly n integers. Whitespace may be spaces or line breaks.

Output: Print the requested sequence on one line with single spaces and no trailing space. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• n is positive and is followed by exactly n signed 32-bit integers.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Maintain a max-heap lower half and min-heap upper half with size difference at most one.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

5 5 2 10 4 3

Sample output

5 3.5 5 4.5 4

Why the sample works: Visible walkthrough for the ordinary non-trivial path. The two heaps split lower and upper values; their roots determine each odd or even prefix median. Input `5 5 2 10 4 3` therefore produces `5 3.5 5 4.5 4`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: Rebalance after every insertion before reading either heap root.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.