Trees · pattern 7 of 8

Heap as a priority queue

A priority queue is a waiting line where the most urgent item leaves first, not the oldest. A heap makes one: a pile that always hands you its largest item (a max-heap) or its smallest (a min-heap). Adding or removing takes about log n steps.

Watch it run in the app

When to use it

Use it when you must take the most urgent item next, again and again, while new items keep arriving and every item waits for its turn.

It belongs to the trees group: Let the shape of the data do the work: the branches of a tree, the letters of a trie, the top of a heap.

Watch it work

A repair shop logs its day in order. A number is a new job with that urgency, and a larger number is more urgent. A 0 means the mechanic is free and takes the most urgent job waiting. Return the jobs in the order they were taken.

Input
events = [2, 5, 0, 3, 1, 0, 4, 0]

Output
[5, 3, 4]

The method

Start with an empty max-heap: its top is the most urgent job
A number is a new job: push it onto the heap
A zero: the mechanic is free and takes the top job
Return the jobs in the order they were taken

The run, one moment at a time

Step 1. No job has arrived yet. The heap of waiting jobs and the list of jobs taken are both empty.
```
events: 2 5 0 3 1 0 4 0
heap: empty
taken: empty
```
Step 2. A job of urgency 2 arrives. Push it. It is the only job waiting, so it is the top of the heap.
```
events: 2 5 0 3 1 0 4 0
heap: 2  (top at 0)
taken: empty
```
Step 2. A job of urgency 5 arrives. Push it. It is the most urgent job waiting, so it is the new top of the heap.
```
events: 2 5 0 3 1 0 4 0
heap: 5 2  (top at 0)
taken: empty
```
Step 3. The mechanic is free. Pop the top, 5, the most urgent job waiting. Job 2 came earlier and still waits: urgency decides, not the order of arrival.
```
events: 2 5 0 3 1 0 4 0
heap: 2  (top at 0)
taken: 5
```
Step 2. A job of urgency 3 arrives. Push it. It is the most urgent job waiting, so it is the new top of the heap.
```
events: 2 5 0 3 1 0 4 0
heap: 3 2  (top at 0)
taken: 5
```
Step 2. A job of urgency 1 arrives. Push it. The job of urgency 3 is more urgent and stays on top.
```
events: 2 5 0 3 1 0 4 0
heap: 3 2 1  (top at 0)
taken: 5
```
Step 3. The mechanic is free. Pop the top, 3, the most urgent job waiting. Job 2 is the new top.
```
events: 2 5 0 3 1 0 4 0
heap: 2 1  (top at 0)
taken: 5 3
```
Step 2. A job of urgency 4 arrives. Push it. It is the most urgent job waiting, so it is the new top of the heap.
```
events: 2 5 0 3 1 0 4 0
heap: 4 1 2  (top at 0)
taken: 5 3
```
Step 3. The mechanic is free. Pop the top, 4, the most urgent job waiting. Job 2 is the new top.
```
events: 2 5 0 3 1 0 4 0
heap: 2 1  (top at 0)
taken: 5 3 4
```
Step 4. The mechanic took 3 jobs, each time the most urgent one waiting: 5, 3, 4. Jobs 2 and 1 never got a turn.
```
events: 2 5 0 3 1 0 4 0
heap: 2 1  (top at 0)
taken: 5 3 4
```

The code

The numbered comments are the steps of the method.

JavaScript

// JavaScript has no built-in heap, so these two helpers keep an array
// in max-heap order by hand: no value is larger than its parent, so
// the largest is at index 0. The parent of index i is at
// (i - 1) >>> 1, which is (i - 1) / 2 rounded down, and its two
// children are at 2 * i + 1 and 2 * i + 2.
function heapPush(heap, x) {
  // The new value starts at the end and swaps with its parent while the
  // parent is smaller.
  heap.push(x);
  let i = heap.length - 1;
  while (i) {
    const p = (i - 1) >>> 1;
    if (heap[p] >= heap[i]) break;
    [heap[p], heap[i]] = [heap[i], heap[p]];
    i = p;
  }
}
function heapPop(heap) {
  // The largest value leaves. The last value takes its place at
  // index 0, then swaps with its larger child while that child is
  // larger.
  const largest = heap[0],
    last = heap.pop();
  if (!heap.length) return largest;
  heap[0] = last;
  let i = 0;
  while (true) {
    let child = 2 * i + 1;
    if (child >= heap.length) break;
    if (child + 1 < heap.length && heap[child + 1] > heap[child]) {
      child++;
    }
    if (heap[i] >= heap[child]) break;
    [heap[i], heap[child]] = [heap[child], heap[i]];
    i = child;
  }
  return largest;
}

function solve(events) {
  // 1. Start with an empty max-heap: its top is the most urgent job
  const heap = [];
  const taken = [];
  for (const event of events) {
    if (event > 0) {
      // 2. A number is a new job: push it onto the heap
      heapPush(heap, event);
    } else {
      // 3. A zero: the mechanic is free and takes the top job
      taken.push(heapPop(heap));
    }
  }
  // 4. Return the jobs in the order they were taken
  return taken;
}

Python

import heapq


def solve(events):
    # 1. Start with an empty max-heap: its top is the most urgent job
    # heapq always has its smallest number on top, so each urgency is
    # stored negated: the smallest stored number is the most urgent job.
    heap = []
    taken = []
    for event in events:
        if event > 0:
            # 2. A number is a new job: push it onto the heap
            heapq.heappush(heap, -event)
        else:
            # 3. A zero: the mechanic is free and takes the top job
            taken.append(-heapq.heappop(heap))
    # 4. Return the jobs in the order they were taken
    return taken

How to spot it

Asked: Take the largest (or smallest) item that is left, again and again: The top of the heap is always that item. After it leaves, the next one comes to the top in about log n steps.
Given: New items arrive, or change, between one take and the next: A sorted list would have to be sorted again after each change. A heap puts one new item in its place in about log n steps.
Limits: Up to 100,000 items, so scanning them all for each take is too slow: Scanning for the largest before every take is about 5 billion comparisons in total. A heap needs about 17 steps for one take.

Looks like it, but is not

Only the k largest values matter, and everything else can be thrown away. Use Heap of the best k. That heap is capped at k, and its top is the value to drop. A priority queue keeps every item until it is taken.
The item to take next is always the newest one, not the largest or the most urgent. Use Last-in, first-out stack. The newest item is at the end of a list, found in one step. Nothing has to be ordered by size.
On a map of roads with lengths, you always go on from the nearest place not yet reached. Use Weighted shortest path. That is a fast way to find shortest routes, and it does use a heap. But the pattern is the search over the map, and its lesson needs no heap.

Cost and mistakes

Each push and each pop takes about log n steps when n jobs are waiting, which is 17 steps for 100,000 jobs. So n events take O(n log n) time at most. Extra space is one heap entry for each waiting job, O(n).

Watch out

Python's heapq always has the smallest on top. To take the largest first, push each value negated, and negate it again when it comes out.
A heap is not sorted. Only its top is in a known place, so never read heap[1] as the second most urgent. Pop the top to see what comes next.

In the 150

2 problems of the 150 use it. Naming them gives their method away, so the list is folded.

Show the 2

Last Stone WeightEasy · Heap / Priority Queue
Minimum Interval to Include Each QueryHard · Intervals