Arrays and searching 0/120

Lesson 6 of 9

Heaps

Keep the smallest item at hand with a binary heap, track the largest k values with a size-k min-heap, and keep a running median with two heaps.

4,723 words · 21 min read

Part 1 of 9 Priority queues

Priority queues

Binary search needs an array that is sorted once and then left alone. In the problems of this lesson the values keep changing: new ones arrive, old ones are used up, and after every change we need the largest value that is left. Here is a game that works this way.

Difficulty tier:Very Easy

You get the weights of some stones. On each turn, the two heaviest stones are smashed together. If they weigh the same, both are destroyed. Otherwise the lighter one is destroyed and the heavier one loses that much weight.

When at most one stone is left, return its weight, or 0 if none is left.

Constraints

  • 1≤1 \le stones.length ≤30\le 30
  • 1≤1 \le stones[i] ≤1000\le 1000

Sample 1 · Input

stones = [2,7,4,1,8,1]

Output

1

Sample 2 · Input

stones = [1]

Output

1

Here is the first sample, one turn per line:

stones           the two heaviest    what the smash leaves2 7 4 1 8 1      8 and 7             a stone of weight 12 4 1 1 1        4 and 2             a stone of weight 21 1 1 2          2 and 1             a stone of weight 11 1 1            1 and 1             nothing1

One stone of weight 1 is left, so the answer is 1. The stone that a smash puts back can land anywhere among the others: the 1 from the first turn is one of the lightest stones, and the 2 from the second turn is the heaviest. So sorting the stones once at the start is not enough.

The direct method reads the whole list on every turn to find the two heaviest stones. Every turn destroys at least one stone, so nn stones last at most n−1n - 1 turns, and the turns read at most n+(n−1)+⋯+2n + (n - 1) + \dots + 2 stones, about n2/2n^2 / 2. For the 30 stones allowed here that is 464 reads, which the judge accepts. A contest problem built on the same loop can have 200,000 values, and then it is about

200,00022=2×1010 reads,\frac{200{,}000^2}{2} = 2 \times 10^{10} \text{ reads,}

which is 200 seconds of work at the rule-of-thumb rate of 10810^8 simple operations a second.

The game does only three things with its stones: it adds one, it reads the heaviest, and it removes the heaviest.

Definition

A priority queue is a collection with three operations: add a value, read the value with the highest priority, and remove that value.

In a max-priority queue the largest value has the highest priority, and in a min-priority queue the smallest.

A plain list, sorted or not, already has these three operations, but not all of them are fast:

Cost of each operation on a max-priority queue of n values
Stored asAddRead the largestRemove the largest
Unsorted listO(1)O(1)O(n)O(n)O(n)O(n)
Sorted listO(n)O(n)O(1)O(1)O(1)O(1)
Binary heapO(log⁡n)O(\log n)O(1)O(1)O(log⁡n)O(\log n)

A sorted list has its largest value at the end, but a new value has to be inserted at its sorted place, which moves every value after it one position along, up to nn of them. Binary search finds that place in O(log⁡n)O(\log n) steps, but the values after it still have to move.

A binary heap sits between the two. It keeps its list only partly ordered: ordered enough that the value with the highest priority is always at the front, and loosely enough that an add or a remove repairs the order in about log⁡2n\log_2 n steps, at most 17 for 200,000 values. Python's and C++'s priority queues are both binary heaps, which is why "heap" and "priority queue" are often used as names for the same thing.