Two Heaps

A max-heap of the smaller half and a min-heap of the larger half, kept balanced. The two heap tops straddle the median, so the median is O(1).

Keep a min-heap of exactly k largest values seen so far; the heap’s minimum is the kth largest.

Repeatedly take the two heaviest stones using a max-heap; smash and push back the remainder until at most one stone remains.

Either maintain a size-k min-heap of the largest values, or partition (QuickSelect) to place the kth largest without full sort.