Smash the heaviest parcels

Scenario

A returns centre in a delivery warehouse has a pressing machine. The machine takes the two heaviest parcels from the pile and presses them together, and the pile changes after every press.

You work on the machine's control software. A pile can hold up to 100,000 parcels, so the machine must find the two heaviest quickly, again and again.

Your task

Write last_parcel(weights).

weights[i] is the weight of parcel i.
In each round, take the two heaviest parcels. If they weigh the same, both are gone. If they differ, the lighter one is gone and the heavier one stays, with its weight reduced to the difference.
Keep going until at most one parcel is left.
Return the weight of the last parcel, or 0 when none is left.

Examples

Example 1 (traced)#

text2 lines

Input:  weights = [2, 7, 4, 1, 8, 1]
Output: 1

Round	Two heaviest	What stays	Pile after
1	8 and 7	1	2, 4, 1, 1, 1
2	4 and 2	2	1, 1, 1, 2
3	2 and 1	1	1, 1, 1
4	1 and 1	nothing	1

One parcel is left, with weight 1.

Example 2#

text2 lines

Input:  weights = [5, 5]
Output: 0

The two parcels weigh the same, so both are gone and nothing is left.

Example 3#

text2 lines

Input:  weights = [3]
Output: 3

A single parcel is already the last one.

Constraints

1 ≤ length of weights ≤ 10^5
1 ≤ weights[i] ≤ 10^6

What does n ≤ 10^5 tell you?

A pile of 100,000 parcels needs up to 99,999 rounds. If each round sorted the whole pile, the machine would do about 100,000 sorts of 100,000 parcels each, which is far too slow.

You only need the two heaviest parcels each round. A structure that keeps the largest item on top, and fixes itself in about 17 steps after each change, fits the job.

Scenario

A returns centre in a delivery warehouse has a pressing machine. The machine takes the two heaviest parcels from the pile and presses them together, and the pile changes after every press.

You work on the machine's control software. A pile can hold up to 100,000 parcels, so the machine must find the two heaviest quickly, again and again.

Your task

Write last_parcel(weights).

weights[i] is the weight of parcel i.
In each round, take the two heaviest parcels. If they weigh the same, both are gone. If they differ, the lighter one is gone and the heavier one stays, with its weight reduced to the difference.
Keep going until at most one parcel is left.
Return the weight of the last parcel, or 0 when none is left.

Examples

Example 1 (traced)#

text2 lines

Input:  weights = [2, 7, 4, 1, 8, 1]
Output: 1

Round	Two heaviest	What stays	Pile after
1	8 and 7	1	2, 4, 1, 1, 1
2	4 and 2	2	1, 1, 1, 2
3	2 and 1	1	1, 1, 1
4	1 and 1	nothing	1

One parcel is left, with weight 1.

Example 2#

text2 lines

Input:  weights = [5, 5]
Output: 0

The two parcels weigh the same, so both are gone and nothing is left.

Example 3#

text2 lines

Input:  weights = [3]
Output: 3

A single parcel is already the last one.

Constraints

1 ≤ length of weights ≤ 10^5
1 ≤ weights[i] ≤ 10^6

What does n ≤ 10^5 tell you?

A pile of 100,000 parcels needs up to 99,999 rounds. If each round sorted the whole pile, the machine would do about 100,000 sorts of 100,000 parcels each, which is far too slow.

You only need the two heaviest parcels each round. A structure that keeps the largest item on top, and fixes itself in about 17 steps after each change, fits the job.