Heaps and Priority Queues

A busy kitchen gets delivery orders all evening. Each one has a pickup time. Whenever a cook is free, they should start the order due soonest. New orders keep arriving while others are cooked, so the list is never finished and never stays in order for long.

You need a container with three operations: add an order, look at the most urgent one, and remove it. That container is called a priority queue. A plain queue hands items out in arrival order. A priority queue hands them out by urgency.

#Three ways to build it

The obvious attempts each make one operation slow.

• Unsorted array: adding is instant, but finding the most urgent order means scanning all of them. O(n) per removal.
• Sorted array: the most urgent is at one end, but every new order must be slotted into place, shifting the others. O(n) per insert.
• Heap: both adding and removing cost O(log n), and looking at the most urgent costs O(1).

With 100,000 waiting items, O(n) is 100,000 steps per operation. O(log n) is about 17.

#A min-heap, briefly

Heap Sort already introduced the max-heap: a binary tree stored in a plain array, where the children of index i sit at 2i + 1 and 2i + 2, and every parent is at least as big as its children. A priority queue for "soonest first" wants the opposite, a min-heap: every parent is at most as big as its children. Then the smallest item is always at the root, heap[0].

Two facts make a heap fast:

• The tree is always filled level by level, left to right. So with n items it is only about log₂ n levels tall.
• The rule only compares parents with children. Siblings and cousins can be in any order. That loose rule is cheap to repair after a change, which is why a heap beats a fully sorted array.

#Push: add at the bottom, sift up

To add an item, put it in the next free slot, at the end of the array. That keeps the tree's shape. The new item might be smaller than its parent, though, so sift it up: while it is smaller than its parent, swap the two. The parent of index i is at (i − 1) / 2, rounded down.

#Pop: move the last item to the top, sift down

The item to remove is the root. You cannot leave a hole at the top, so take the last item in the array, put it at the root, and shorten the array by one. That item is probably too big for the top, so sift it down: swap it with its smaller child until it is no bigger than both children. This is the same sift-down as in heap sort, with "bigger" turned into "smaller".

Here are both, on orders that are due in 2, 4, 5, 7, 8 and 9 minutes. A new order due in 3 minutes arrives, and then a cook takes the most urgent order.

push(x):  add x at the end  while x < its parent: swap thempop():  top = heap[0]  move the last item to index 0  while it > its smaller child: swap them  return top

#The code

The heap is a plain array. These two functions keep it in min-heap order.

// heap is a plain array kept in min-heap order.
function heapPush(heap, x) {
  heap.push(x); // add at the end of the bottom level
  let i = heap.length - 1;
  while (i > 0) {
    const parent = Math.floor((i - 1) / 2);
    if (heap[parent] <= heap[i]) break; // parent is smaller: done
    [heap[parent], heap[i]] = [heap[i], heap[parent]];
    i = parent; // keep climbing
  }
}

# heap is a plain list kept in min-heap order.
def heap_push(heap, x):
    heap.append(x)  # add at the end of the bottom level
    i = len(heap) - 1
    while i > 0:
        parent = (i - 1) // 2
        if heap[parent] <= heap[i]:  # parent is smaller: done
            break
        heap[parent], heap[i] = heap[i], heap[parent]
        i = parent  # keep climbing

function heapPop(heap) {
  const top = heap[0];
  const last = heap.pop(); // remove the last item
  if (heap.length === 0) return top; // it was the only one
  heap[0] = last; // move it to the root and sift down
  let i = 0;
  while (true) {
    const left = 2 * i + 1, right = 2 * i + 2;
    let small = i;
    if (left < heap.length && heap[left] < heap[small]) small = left;
    if (right < heap.length && heap[right] < heap[small]) small = right;
    if (small === i) break; // smaller than both children: done
    [heap[i], heap[small]] = [heap[small], heap[i]];
    i = small;
  }
  return top;
}
 
const heap = [2, 5, 4, 9, 7, 8];
heapPush(heap, 3); // [2, 5, 3, 9, 7, 8, 4]
heapPop(heap);     // 2, heap is now [3, 5, 4, 9, 7, 8]

def heap_pop(heap):
    top = heap[0]
    last = heap.pop()  # remove the last item
    if not heap:  # it was the only one
        return top
    heap[0] = last  # move it to the root and sift down
    i = 0
    while True:
        left, right = 2 * i + 1, 2 * i + 2
        small = i
        if left < len(heap) and heap[left] < heap[small]:
            small = left
        if right < len(heap) and heap[right] < heap[small]:
            small = right
        if small == i:  # smaller than both children: done
            break
        heap[i], heap[small] = heap[small], heap[i]
        i = small
    return top
 
heap = [2, 5, 4, 9, 7, 8]
heap_push(heap, 3)  # [2, 5, 3, 9, 7, 8, 4]
heap_pop(heap)      # 2, heap is now [3, 5, 4, 9, 7, 8]

Python ships these in its heapq module: heapq.heappush(heap, x) and heapq.heappop(heap) work on a plain list exactly like the functions above, and heapq.heapify(list) turns a list into a heap in O(n). JavaScript has no built-in heap, so you copy these two functions or use a library.

To attach data to a priority, push pairs. In Python, (pickup_time, order_id) tuples compare by the first item, then the second. In JavaScript, < does not compare arrays the way you want, so store [time, order] and compare heap[i][0].

#The top k trick

A game has a million scores and you want the 3 highest. Sorting everything costs O(n log n) and keeps all n in memory. A heap does better, and the surprising part is that you want a min-heap.

Keep a min-heap of the best 3 seen so far. Its root is the weakest of those 3, the score a newcomer has to beat. Push each new score; if the heap grows to 4, pop the smallest. At the end, the heap holds the top 3.

// Uses heapPush and heapPop from above.
function topK(nums, k) {
  const heap = [];
  for (const x of nums) {
    heapPush(heap, x);
    if (heap.length > k) heapPop(heap); // drop the smallest
  }
  return heap.sort((a, b) => a - b);
}
 
topK([40, 95, 12, 77, 63, 88], 3); // [77, 88, 95]

import heapq
 
def top_k(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)  # drop the smallest
    return sorted(heap)
 
top_k([40, 95, 12, 77, 63, 88], 3)  # [77, 88, 95]

The heap never holds more than k + 1 items, so each push and pop costs O(log k). The whole run is O(n log k) time and O(k) space. For the top 10 of a million, log k is about 3, against about 20 for a full sort.

#Common mistakes

#Check yourself

#What to practise next

Heaps order items by a number. When your keys are words and you need prefix questions, such as "every saved contact starting with sam", the tool is a different tree: Tries.