Quickselect, not a heap — because the point of this problem is partitioning.
One Lomuto sweep with pivot at the end and two pointers
(i, the boundary of the “less than pivot” prefix, and
j, the reader) drops the pivot at its final sorted index.
Compare that index to target = n − k and you know which side the answer is on,
so you recurse into one side and throw the other away forever. That discard is the
whole algorithm; everything greyed out below is work you never do.
n + n/2 + n/4 + … = 2n. Worst case is O(n²) when the pivot is always
extreme (run the already-sorted example and watch the range shrink by one);
a randomised pivot makes that vanishingly unlikely. A size-k heap instead gives a
guaranteed O(n log k) with O(k) space, and — unlike quickselect —
never reorders the input.