= Solution
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,
$$
\boxed{\text{the heap root is the }k\text{th smallest input value}.}
$$
Construction costs $O(k)$; each remaining value uses one comparison and at most one logarithmic repair. Thus the <selection algorithm> has <time complexity>
$$
\boxed{O\bigl(n+(n-k)\log k\bigr)=O(n\log k)\quad(k\ge2),\qquad O(k)\ \text{space}.}
$$
For $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.
Back to article page
