Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 7 / d

Assume $1\le k\le n$. Use bottom-up heap construction to make a max-heap of the first $k$ input items. For each subsequent input value $x$, compare it with the root. If $x$ is at least the root, discard it; otherwise replace the root by $x$ and apply heapify down. Return the final root.

The loop invariant says the heap contains a multiset of the $k$ smallest values seen so far. It holds after initialization. If $x$ is at least the current largest retained value, the already retained $k$ items are no larger, so discarding $x$ preserves the invariant. If $x$ is smaller, remove one largest retained value and keep $x$ instead; precisely the $k$ smallest values remain. This argument handles equal integers by treating repeated occurrences as separate items. At the end,Construction costs $O(k)$; each remaining value uses one comparison and at most one logarithmic repair. Thus the selection algorithm has time complexityFor $k=1$, the heap is a single running minimum and the time is $O(n)$. The uniform expression $O(n\log (k+1))$ covers that boundary; interpreting the printed $O(n\log k)$ literally at $k=1$ would incorrectly make it zero.