Last Stone - Algorithm

Use a max-heap to always get the two heaviest stones:

$1.$ Insert all stones into a max-heap.

$2.$ While heap has more than one stone:

• Extract the two largest: $y$ and $x$ (with $y \geq x$)
• If $y > x$, insert $y - x$ back into the heap

$3.$ Return the remaining stone's weight, or $0$ if empty. Each smash involves at most two extractions and one insertion: $O(\log n)$ per turn, at most $n$ turns. Time: $O(n \log n)$. Space: $O(n)$.