872. The Smallest Still Waiting
A counter processes a log of q operations, each on its own line:
push v a ticket numbered v joins the queue
take the SMALLEST numbered ticket waiting is called and leaves
For every take, print the number called. If nothing is waiting, print
empty instead and the operation does nothing.
push 5, push 2, take, push 9, take, take -> 2, 5, 9
take, push 4, take -> empty, 4
push 7, push 7, take, take -> 7, 7
Trace the first one. After push 5 and push 2 the waiting set is
5, 2, so take calls 2. Then 9 joins, the set is 5, 9, and the next
take calls 5, then the last one calls 9.
## What most people try first
A sorted array. Keep the waiting tickets in increasing order, and take
is just "read the front". The problem is push. Putting 2 in front of 5
means shifting everything after the insertion point, which is O(n) per
push. With q = 200000 pushes that is about 2 * 10^10 element moves.
A sorted array is wonderful until something is inserted into it.
An unsorted array. Now push is free, and take has to scan everything
to find the minimum. That is O(n) per take, which is the same
2 * 10^10 from the other side.
The two failures are mirror images, and that is the hint: the structure you want is the one that refuses to do either job perfectly.
## The heap
A binary heap keeps the values in an array under a single rule: the value at
position i is no larger than the values at positions 2i + 1 and
2i + 2. That is much weaker than sorted order, and it is exactly strong
enough to put the minimum at position 0.
``` push v: put v at the end while v is smaller than its parent, swap them (sift up)
take: answer = position 0 move the last value to position 0 and shrink while it is larger than its smaller child, swap them (sift down) ```
## Why it is correct, and why it is fast
The rule says every parent beats both children, so by following the rule from the root downwards, the root beats everything. It is the minimum.
Both repair loops walk one root-to-leaf path. A binary heap of n values is
a complete tree, so its height is floor(log2 n), which at n = 200000 is
17. Seventeen swaps in the worst case instead of two hundred thousand shifts.
## The boundary that breaks a careless implementation
take on an empty heap. Reading position 0 of an empty array is either a
crash or a silently wrong answer depending on the language, and the log is
allowed to start with take. Check the size FIRST, print empty, and do
not touch the heap.
The second one: after removing the root you must move the LAST value to the root and then sift down. Moving the smaller child up and leaving a gap makes the array stop being a complete tree and every later index calculation is off.
## Output when nothing is asked
A log made only of pushes produces no lines at all. Print none in that
case, so that the answer is never an empty file.
## What is NOT an overflow here
Values reach 10^9 in magnitude and nothing is ever added, multiplied or
accumulated. The largest signed 32-bit integer is 2147483647, so every
value fits with room to spare and no type here needs widening. Problem 877,
which adds to a value repeatedly, is where that stops being true.
## Related problems
Problem 873 is this log with the direction flipped and a tie rule attached. Problem 879 is a deliberate counterweight: it asks a ranked question about a collection that never changes, where a heap is the WRONG tool.
## Cost
Time O(q log q). Space O(q).
Constraints - `1 ≤ q ≤ 200000` - `-1000000000 ≤ v ≤ 1000000000`
Input
The first line contains one integer q.
Each of the next q lines is either push v with an integer v, or the single word take.
Output
Print one line for every take operation, in order: the smallest waiting value, or the word empty if nothing is waiting. If the log contains no take at all, print the single word none.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.