Trees · pattern 8 of 8

Two heaps

A heap is a pile that always shows its largest item, or its smallest, and takes about log n steps to add or remove one. Keep the smaller half of the numbers in one heap, the larger half in another. Their tops are the middle.

Watch it run in the app

When to use it

Use it when you need the middle value again and again while numbers keep arriving: keep a smaller half and a larger half, and read their tops.

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 market stall sells melons. A number is the weight of a melon put on the stall. A 0 means a customer buys the middle melon by weight; with an even number of melons, the lighter of the two middle ones. Return the weights sold, in order.

Input
events = [5, 2, 0, 8, 3, 0]

Output
[2, 5]

The method

Keep the smaller half in a max-heap, the larger in a min-heap
A new weight goes into the smaller half first
The top of the smaller half moves to the larger half
A buyer takes the top of the smaller half: the middle
If the larger half now holds more, move its top back
Return the weights sold, in order

The run, one moment at a time

Step 1. The stall is empty. The small half will show its heaviest melon on top, and the large half its lightest.
```
events: 5 2 0 8 3 0
small: empty
large: empty
sold: empty
```
Step 2. A melon of 5 arrives. It goes into the small half first, whichever half it belongs in.
```
events: 5 2 0 8 3 0
small: 5  (top at 0)
large: empty
sold: empty
```
Step 3. The top of the small half, 5, moves over. This way no melon in the small half is ever heavier than one in the large half.
```
events: 5 2 0 8 3 0
small: empty
large: 5  (top at 0)
sold: empty
```
Step 5. The large half held 1 and the small half only 0. The top of the large half, 5, moves back, so the middle is on top of the small half again.
```
events: 5 2 0 8 3 0
small: 5  (top at 0)
large: empty
sold: empty
```
Step 3. 2 goes into the small half. The top of that half is 5, not 2, so 5 moves over to the large half. Both halves now hold 1.
```
events: 5 2 0 8 3 0
small: 2  (top at 0)
large: 5  (top at 0)
sold: empty
```
Step 4. A customer comes. The stall holds 2 and 5, an even number, so the lighter of the two middle melons is sold: 2, the top of the small half.
```
events: 5 2 0 8 3 0
small: empty
large: 5  (top at 0)
sold: 2
```
Step 5. The large half held 1 and the small half only 0. The top of the large half, 5, moves back, so the middle is on top of the small half again.
```
events: 5 2 0 8 3 0
small: 5  (top at 0)
large: empty
sold: 2
```
Step 3. 8 goes into the small half and is the heaviest there, so it moves straight over to the large half. Both halves now hold 1.
```
events: 5 2 0 8 3 0
small: 5  (top at 0)
large: 8  (top at 0)
sold: 2
```
Step 3. 3 goes into the small half. The top of that half is 5, not 3, so 5 moves over to the large half.
```
events: 5 2 0 8 3 0
small: 3  (top at 0)
large: 5 8  (top at 0)
sold: 2
```
Step 5. The large half held 2 and the small half only 1. The top of the large half, 5, moves back, so the middle is on top of the small half again.
```
events: 5 2 0 8 3 0
small: 5 3  (top at 0)
large: 8  (top at 0)
sold: 2
```
Step 4. A customer comes. The stall holds 3, 5 and 8. The middle melon is 5, the top of the small half. Pop it: it is sold.
```
events: 5 2 0 8 3 0
small: 3  (top at 0)
large: 8  (top at 0)
sold: 2 5
```
Step 6. The customers bought 2 melons, each one the middle of the stall at that moment: 2, then 5.
```
events: 5 2 0 8 3 0
small: 3  (top at 0)
large: 8  (top at 0)
sold: 2 5
```

The code

The numbered comments are the steps of the method.

JavaScript

// JavaScript has no built-in heap, so these helpers keep an array in
// heap order by hand. onTop(a, b) says whether a belongs nearer the top
// than b: the two functions below make a min-heap or a max-heap. The
// value that belongs on top 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.
const smallestOnTop = (a, b) => a < b;
const largestOnTop = (a, b) => a > b;
function heapPush(heap, x, onTop) {
  // The new value starts at the end and swaps with its parent while it
  // belongs above that parent.
  heap.push(x);
  let i = heap.length - 1;
  while (i) {
    const p = (i - 1) >>> 1;
    if (!onTop(heap[i], heap[p])) break;
    [heap[p], heap[i]] = [heap[i], heap[p]];
    i = p;
  }
}
function heapPop(heap, onTop) {
  // The top value leaves. The last value takes its place at index 0,
  // then swaps with the child that belongs higher, while that child
  // belongs above it.
  const top = heap[0],
    last = heap.pop();
  if (!heap.length) return top;
  heap[0] = last;
  let i = 0;
  while (true) {
    let child = 2 * i + 1;
    if (child >= heap.length) break;
    const other = child + 1;
    if (other < heap.length && onTop(heap[other], heap[child])) child++;
    if (!onTop(heap[child], heap[i])) break;
    [heap[i], heap[child]] = [heap[child], heap[i]];
    i = child;
  }
  return top;
}

function solve(events) {
  // 1. Keep the smaller half in a max-heap, the larger in a min-heap
  const small = [];
  const large = [];
  const sold = [];
  for (const event of events) {
    if (event > 0) {
      // 2. A new weight goes into the smaller half first
      heapPush(small, event, largestOnTop);
      // 3. The top of the smaller half moves to the larger half
      heapPush(large, heapPop(small, largestOnTop), smallestOnTop);
    } else {
      // 4. A buyer takes the top of the smaller half: the middle
      sold.push(heapPop(small, largestOnTop));
    }
    // 5. If the larger half now holds more, move its top back
    if (large.length > small.length) {
      heapPush(small, heapPop(large, smallestOnTop), largestOnTop);
    }
  }
  // 6. Return the weights sold, in order
  return sold;
}

Python

import heapq


def solve(events):
    # 1. Keep the smaller half in a max-heap, the larger in a min-heap
    # heapq is a min-heap. The smaller half is stored negated, so the
    # top of its heap is the largest weight of that half.
    small = []
    large = []
    sold = []
    for event in events:
        if event > 0:
            # 2. A new weight goes into the smaller half first
            heapq.heappush(small, -event)
            # 3. The top of the smaller half moves to the larger half
            heapq.heappush(large, -heapq.heappop(small))
        else:
            # 4. A buyer takes the top of the smaller half: the middle
            sold.append(-heapq.heappop(small))
        # 5. If the larger half now holds more, move its top back
        if len(large) > len(small):
            heapq.heappush(small, -heapq.heappop(large))
    # 6. Return the weights sold, in order
    return sold

How to spot it

Asked: Report the median after each new number: The median, the middle value in sorted order, is where the smaller half meets the larger half. Both tops stand at that border.
Given: A growing collection of numbers, and the middle is asked for many times: Sorting again for each question is too slow. Two heaps keep the middle on top while numbers are added.
Asked: Split the values into a lower half and an upper half: A max-heap, largest on top, holds the lower half. A min-heap, smallest on top, holds the upper half. Moving one top across keeps the sizes the same, or one apart.
Limits: Up to 100,000 numbers, and the middle is asked for after each: Sorting before every question is far too slow. A push or a pop takes about 17 steps, and the middle is read in one.

Looks like it, but is not

Only the k largest values matter, and the middle is never asked for. Use Heap of the best k. One heap capped at k is enough. Everything outside the best k is thrown away, so there is no second half to keep.
You take the largest (or the smallest) value again and again, never the middle one. Use Heap as a priority queue. One heap already shows one end of the values. A second heap is needed only to reach the middle.
You must find the middle node of a linked list. Use Fast and slow pointers. That middle is a position, not a value. Walk the list at two speeds; no numbers are compared.

Cost and mistakes

Adding a number, or taking the middle one out, is at most five pushes and pops of about log n steps each, O(log n). Reading the middle is one step, O(1): it is on top. Extra space is one entry for each number kept, O(n).

Watch out

Compare the two sizes after every change. If one half holds two more than the other, its top is no longer the middle.
Python's heapq is only a min-heap. Store the smaller half negated, and negate a value again when it leaves that half.

In the 150

One problem of the 150 uses it. Naming them gives their method away, so the list is folded.

Show it

Find Median From Data StreamHard · Heap / Priority Queue