Pattern visualizer
Last Stone Weight
Every round needs the current two heaviest stones, and after a smash the survivor re-enters the pool at an unpredictable rank. Re-sorting the whole pool each round works but wastes effort on stones that never moved. A max-heap keeps exactly what the round needs — the largest value — at the root, and restores that property in O(log n) after each change instead of O(n log n). Animated on: stones = [2,7,4,1,8,1] — repeatedly smash the two heaviest stones together (equal weights destroy both, otherwise the heavier one survives at weight difference) until at most one remains. Expected: 1..
Max-heap: always smash the two heaviest
Stones [2, 7, 4, 1, 8, 1] load into an array. Read as a heap it is unordered — slot i's children live at 2i+1 and 2i+2, but nothing yet guarantees a parent outweighs them.
1FUNCTION lastStoneWeight(stones):2 BUILD max-heap H from stones3 WHILE SIZE(H) > 1:4 a <- EXTRACT-MAX(H)5 b <- EXTRACT-MAX(H)6 IF a != b:7 INSERT(H, a - b)8 IF SIZE(H) = 1: RETURN H[0]9 ELSE: RETURN 0
← / → step · space play · Home restart