sdlc.dev

Data structures and algorithms path · Putting things in order · Topic 9 of 13

Heaps and priority queues

Not started

A priority queue lets you add items in any order and always take out the smallest (or most urgent) one next. The standard way to build it is a binary heap: a binary tree, stored flat in an array, where every parent is smaller than or equal to its children. That partial order is cheap to maintain, O(log n) per insert or removal, and it is all you need to find the minimum, which always sits at index 0.

Why it matters: Schedulers, timers, Dijkstra's shortest paths, merging sorted streams and "top 10" queries all need the next-most-important item without sorting everything.

  1. 1A tree stored in an array

    A binary heap is a complete binary tree laid out level by level: the children of index i are at 2i + 1 and 2i + 2, its parent at (i − 1) / 2, rounded down.

  2. 2Parents beat children

    In a min-heap every parent is ≤ its children, so the minimum is always at index 0. Nothing else is sorted.

  3. 3O(log n) push and pop

    Push adds a leaf and swaps it upwards; pop moves the last leaf to the root and swaps it downwards. Both walk one path.

  4. 4A priority queue is the interface

    "Insert" and "remove the most urgent" is the abstract idea; a binary heap is the usual way to build it.

1

Watch it run

Play it or step through. Every step says what just happened.

const heap = [];function push(x) {  heap.push(x);  let i = heap.length - 1;  while (i > 0) {    const parent = (i - 1) >> 1;    if (heap[parent] <= heap[i]) break;    [heap[parent], heap[i]] = [heap[i], heap[parent]];    i = parent;  }}for (const x of [5, 3, 8, 1]) push(x);console.log(heap.join(" "));

Still to push

empty

Heap array (index 0 first)

Children of index i live at 2i + 1 and 2i + 2

empty

Comparing

The new item and its parent

empty

Console0 lines

    Step 0 of 11

    Nothing has run yet. The heap is an ordinary array; the tree exists only in the index arithmetic.

    Popping the minimum is the mirror image. Move the last item to index 0, then swap it with its smaller child until both children are larger.

    2

    Try it yourself

    Change the code, predict the order, then run it for real in your browser.

    ⌘/Ctrl + Enter
    OutputNot run yet

    Press Run to see what your code prints, in order.

    Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

    3

    Check yourself

    3 questions. Get them all right to finish this topic.

    1. 1.In a min-heap stored as an array, where is the parent of the item at index 9?
    2. 2.Is the array of a valid min-heap sorted?
    3. 3.You need the 10 largest values from a stream of a billion numbers. What is the memory-efficient approach?

    0 of 3 right so far. Get all three to finish this topic.

    Pop: sift down

    Removing the minimum takes the item at index 0, moves the last leaf into its place and pushes it down, swapping with the smaller of its two children until neither child is smaller. Again one path, so O(log n):

    ⌘/Ctrl + Enter
    OutputNot run yet

    Press Run to see what your code prints, in order.

    Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

    Popping everything returns the items in sorted order. That is heapsort: O(n log n), in place, but not stable, and it jumps around memory, so in practice it is mostly used as a safety net inside other sorts.

    Where heaps show up

    • Schedulers and timers: the next job or timeout to fire is the minimum by time. Many event loops keep their timers in a heap.
    • Dijkstra's algorithm and A*: the next node to explore is the one with the smallest known distance.
    • Merging k sorted lists: keep the head of each list in a heap and repeatedly take the smallest (heapq.merge in Python).
    • Top-k: a min-heap of size k over a stream, as above, uses O(k) memory however long the stream is.

    Building a heap from n items you already have can be done in O(n), not O(n log n), by sifting down from the middle of the array to the front (heapq.heapify). Python's heapq works on plain lists as a min-heap; Java has PriorityQueue; JavaScript has no built-in heap, so you write one like the above or use a library. A heap can't find or remove an arbitrary item quickly, so to change a priority you usually push a new entry and skip stale ones when they come out.

    Go deeper