The earliest deadline first article gave you the scheduler’s rule - serve the task due soonest - but not the machinery. This article covers that machinery. A scheduler asks the same question thousands of times a day: of everything waiting, which task has the smallest due time? A naive scan walks the whole queue for every answer. A heap keeps the smallest item one step away, so the “Up next” list can be recomputed as soon as you solve something. A heap is the priority queue made concrete, and the priority queue is the scheduler’s one data structure.
A priority queue is the scheduler’s abstraction
Start with the behavior, not the tree. A normal queue serves items in arrival order: first in, first out. A priority queue serves items in priority order: the most urgent thing first, regardless of when it arrived. Wengrow’s A Common-Sense Guide to Data Structures and Algorithms defines it as “a list whose deletions and access are just like a classic queue but whose insertions are like an ordered array” - you only take from the front, but new insertions keep the highest-priority item there.
The book uses an emergency room as its example. Patients are not seen in the order they arrive; the order depends on the severity of their condition. A life-threatening case moves ahead of the flu patient who arrived hours earlier. Your review queue uses the same abstraction with a different key. The “severity” is due-ness: an overdue exercise is the critical patient, while a new exercise with no due date yet can wait. The scheduler is a priority queue keyed by due time, and the earliest deadline first rule tells it what to pop from the front.
defmodule MinHeap do
# A min-heap as an ascending list: the head is always the smallest.
# A real heap does push/pop in O(log n) with a tree; this sorted-list
# version is O(n) per push but identical in observable behavior.
def new, do: []
def push(heap, item), do: Enum.sort([item | heap])
def peek([head | _]), do: head
def pop([head | rest]), do: {head, rest}
end
# A scheduler is a min-heap keyed by due time: always pop the task due
# soonest, exactly like the site's "Up next" list.
heap = MinHeap.new()
heap = MinHeap.push(heap, {1, "email"})
heap = MinHeap.push(heap, {5, "report"})
heap = MinHeap.push(heap, {3, "review"})
{soonest, _} = MinHeap.pop(heap)
IO.inspect(soonest, label: "next task (earliest due)")
Run it. The answer is {1, "email"} - not the first task you added, but the one with the smallest key. That is the entire scheduler in four lines. The sorted-list version is honest but slow: every push re-sorts, so one push does work. The heap exists to make both operations fast.
The heap: a tree with one rule
A heap is a binary tree with one ordering constraint and one shape constraint. Both are simple. The ordering is the heap condition: in Wengrow’s words, “each node’s value must be greater than each and every one of its descendants.” That is a max-heap. A min-heap flips the rule, so each node is smaller than all of its descendants. The shape is completeness: every level is full except possibly the last, and the last fills from left to right with no gaps. A heap is a complete tree whose nodes obey the heap condition. Everything else follows from those two constraints.
The first consequence matters most for a scheduler: the root is always the extreme. In a min-heap, the root is the smallest element. To answer “which task is due soonest?”, look at the root - one step, no scan. That is the structure’s job and why it belongs in a priority queue. Wengrow puts it plainly: “the root node will always have the greatest value… this will be the key as to why the heap is a great tool for implementing priority queues.”
The extreme stays one step away while the heap changes. Insert a new value in the next open leaf slot, then trickle it up - swap it with its parent until the heap condition returns. Remove the root by moving the last node into the empty spot, then trickle it down, swapping with the smaller child until order returns. Both walks are bounded by the tree’s height, which is about because the tree is complete. Insert and delete are . That is the whole point: a priority queue that cannot find its minimum in and update in is not worth building.
Weakly ordered, on purpose
This is where people new to heaps usually go wrong: a heap is less ordered than it looks. It is not a binary search tree, and it does not try to be one. In a binary search tree, you know which subtree to descend into to find a value. In a heap, you only know that a value is below some ancestor; you do not know which child contains it. Wengrow’s verdict: “heaps are said to be weakly ordered as compared to binary search trees.”
That weakness is a feature. A heap is not for searching - you cannot efficiently find “the value 7” in one, and you should not try. It handles two operations: read the extreme and update the extreme. By giving up total order, the heap makes insert-and-rebalance cheaper than the work a self-balancing search tree would need, then spends that saving on the operation a scheduler performs constantly. The binary trees article covers the search tree’s total order; the heap uses the same tree shape for a different job. Keep the structures separate: a tree is not a heap is not a search tree, and each is optimal for one kind of question.
The min-heap of size k
The scheduler is one use. Another canonical heap move is to keep the heap small on purpose. It is the trick behind the site’s Kth Largest Element exercise. The problem is to find the th largest element in a stream of numbers. Maintain a min-heap of size containing only the largest values seen so far. For each new number, push it, then pop the smallest if the heap contains items. At the end, the root - the smallest element in the heap - is the th largest value in the stream because it is the smallest of the largest values.
nums = [3, 2, 1, 5, 6, 4]
kth_largest =
nums
|> Enum.reduce(MinHeap.new(), fn n, h ->
h = MinHeap.push(h, n)
if length(h) > 2, do: elem(MinHeap.pop(h), 1), else: h
end)
|> MinHeap.peek()
IO.inspect(kth_largest, label: "kth largest (k=2)")
The result is 5. The direction of the heap makes this work: you want the largest elements, so keep a min-heap. The element you can discard is the smallest one you are keeping, and the min-heap puts it at the root. A max-heap puts the largest element at the root, leaving you unable to find the smallest element to evict without a scan. Build this exercise yourself in the language of your choice. The seeded test cases include duplicates and the single-element edge cases that catch the two most common mistakes.
Where to go next
- Kth Largest Element in an Array - the min-heap-of-size-k trick, with public cases that pin the direction of the heap.
-
Earliest deadline first
- the scheduler’s rule; this article is the structure that runs it.
-
Binary trees: where the log lives
- the tree shape a heap shares, and the total order a heap deliberately gives up.
- Sorting: the wall at n log n - heapsort is the heap turned into a full sort, and the here is the same log this article’s trickle walks.
-
Greedy: when the local choice is the global one
- the scheduling rule the heap’s priority queue serves.
The heap is a small idea with a big job: a complete tree obeying one comparison rule, so the smallest (or largest) item is always one step away. That is the guarantee a scheduler needs. It is why the structure appears behind every system that must answer “what is the most urgent thing right now?” - an operating system’s run queue, a hospital’s triage board, and your review schedule. The “Up next” list recomputes in an instant for the same reason an emergency room triages in an instant: someone built a heap, and the extreme is always at the root.