The stone collision game

You have a pile of stones. On each turn, you pick the two heaviest and smash them together. If they weigh the same, both are destroyed. If not, the lighter one is destroyed and the heavier one loses as much weight as the lighter one had.

Keep going until at most one stone is left.

Always heaviest: the two largest stones collide first.

Reinsert the leftover: if any weight remains, put it back in the heap.

stones in a max-heap (heaviest first)

left: 6

The two heaviest: 8 and 7. They smash; 8 − 7 = 1 survives.

Move 1 of 5

Using a Max-Heap

A max-heap keeps the largest element at the top. In C++, the priority queue is a max-heap by default. In Java, give the PriorityQueue a reverse-order comparison. In Python, which only has a min-heap, store each number as its negative, so the largest becomes the smallest.

Just remember to flip the sign again when you take a number out.

C++: the priority queue is a max-heap by default.

Java: pass a reverse-order comparison to the PriorityQueue.

Python trick: negate numbers so the largest becomes the smallest.

In code

import heapq

heap = [-s for s in stones]
heapq.heapify(heap)
while len(heap) > 1:
    y = -heapq.heappop(heap)
    x = -heapq.heappop(heap)
    if y > x:
        heapq.heappush(heap, -(y - x))
return -heap[0] if heap else 0