Heaps and Priority Queues

You are about to meet a tool that the entire field of AI leans on whenever it must repeatedly pick the best next thing. Once you can build a heap, you can build a priority queue — and that queue is what makes a chatbot decide which of its unfinished thoughts to continue next, what a route-finding app does when it hops from city to city, and how a hospital triages patients. Master this and you unlock the machinery of scheduling, graph search (Dijkstra, A*), and the event loops that drive real-time systems. It also introduces you to the idea of a 'loop invariant' — a property that stays true no matter how many steps you take — which is the backbone of proving that any algorithm actually works. Your library notes say the heap property is weaker than full sorting, and that is exactly why it is cheap to maintain.

Imagine you keep a to-do list, and you always want to do the most urgent thing first. If you wrote every task on paper in random order, you would have to scan the whole list each time to find the most urgent — that is slow when the list is long. If you sorted the list once, finding the most urgent is instant, but inserting a new task and keeping the whole list sorted is also costly. A heap is a middle path: it keeps the list in a shape where the most urgent item is always at the top, but it does not care about the exact order of the rest. This partial order is enough to get the top item instantly, and it lets you insert a new item or remove the top item in a only a few steps — proportional to the height of the tree, which grows very slowly. So you get the best of both worlds: cheap access to the top, and cheap updates. It is a classic trade-off: the heap gives up the strict ordering of the whole list, and in return it buys speed.

Think of a hospital emergency room with a single doctor. Patients arrive at all times, and each has a severity score. The doctor needs to see the most severe patient next. If she kept a paper list in arrival order, she would have to survey everyone each time to find the worst — that is slow and error-prone. If she asked everyone to line up in sorted order, a new patient would have to shuffle into position, and rearranging the whole line is also costly. The heap is like a triage board where the most severe case is always pinned at the top of the board, visible at a glance, and the rest are arranged in a rough hierarchy: each patient's name is above anyone less severe than them, but there is no strict left-to-right order. When a new patient arrives, the nurse writes their name at the bottom of the board and then lets them 'bubble up' — swapping with the person directly above until the hierarchy is restored. When the doctor takes the top patient, the nurse moves the bottom name to the top and lets it 'sink down' — swapping with the more severe of the two below — until the top is the most severe again. The board never becomes fully sorted, but it never has to be: the doctor only ever reads the top. The analogy breaks when you remember that in a heap, the board is not a flat list but a tree-like structure where each node has at most two children. But the key idea — quick access to the extreme, and lazy maintenance of the rest — is exactly what a heap is.

A heap is a complete binary tree where every node is at least as extreme (min or max) as its children, ensuring the extreme element is always at the root, and supporting insert and extract operations in logarithmic time.

You have notes on balanced trees and B-trees — heaps are another kind of tree, but they are not balanced in the same way; they only maintain a partial order. You also have notes on binary tree traversal; a heap is a binary tree, though you do not often traverse it in order because there is no meaningful in-order. Your library says the heap property is weaker than full sorting, which is why it is cheaper to maintain — that is the connection to your notes on sorting algorithms like merge sort and quicksort. A heap is a way to keep the smallest (or largest) element always ready, without paying for a full sort. This is the idea behind priority queues, which are what Dijkstra and scheduling use.