While scanning a file containing 1 million items once and retaining only 10…

Concept:

For a top-K query over a stream, keep K candidates and repeatedly compare each new value with the smallest retained candidate. The required structure must expose that boundary in O(1) time and support its replacement in O(log K) time while using O(K) space.

Application:

1. Read the first 10 items and build a min-heap of those candidates.

2. For each remaining item, compare it with the root, which is the smallest retained value and is available in O(1) time.

3. Discard a value no larger than the root; otherwise replace the root and restore the heap in O(log 10) time.

4. After the scan, every discarded value is no larger than the final boundary, so the heap contains the 10 largest items.

Cross-check:

For K = 10, the bounded min-heap uses O(10) space and O(N log 10) total update time. A max-heap exposes the largest rather than the replacement boundary. An ordinary BST needs O(h) time to reach its minimum and has no balance guarantee, while a sorted 10-element array exposes its minimum in O(1) but may shift O(10) values per replacement. Thus the min-heap uniquely provides the two operation bounds stated in the stem.