Trees and heaps guide · 6/6

Trees and Heaps in the Real World

You will meet trees and heaps far more often as ready-made components than as code you write yourself. This chapter shows where they appear in real systems and which pitfalls catch people when using the standard libraries.

Where they show up

Hierarchical data: file system directories, the browser DOM, a compiler's abstract syntax tree (AST), and JSON or XML documents are all trees. Computing folder sizes is a post-order traversal; rendering a page follows a pre-order walk.
Database indexes: the default indexes in PostgreSQL, MySQL (InnoDB) and SQLite are B-tree variants. Each node holds hundreds of keys, which keeps the height around 3 or 4 and cuts the number of disk reads. Conceptually, it is a BST widened to many branches.
Sorted maps and sets: C++ std::map and std::set (red-black trees in the major implementations) and Java TreeMap and TreeSet (red-black trees) keep keys ordered and answer nearest-value queries such as floorKey or lower_bound in O(log n).
Operating system schedulers: the Linux kernel keeps runnable tasks in a red-black tree to pick the next task quickly.
Timers and event loops: libuv (used by Node.js) and the Go runtime keep timers in min-heap style structures so the next timer to fire is always at hand.
Graph algorithms: Dijkstra's shortest paths, Prim's minimum spanning tree and A* search all pull "the closest candidate so far" from a priority queue.
Stream processing: top-K aggregation, external sorting that merges many sorted files, and event-driven simulation all rely on heaps.

Pitfalls with Python heapq

heapq is a set of functions that treat a plain list as a min-heap. The usual way to get a max-heap is to push negated values (Python 3.14 also adds max-heap functions such as heappush_max). When two priorities tie, tuple comparison moves on to the next element, and an incomparable object such as a dict raises TypeError. Putting an increasing counter in the middle fixes this and also keeps equal priorities in insertion order.

import heapq
import itertools

queue, counter = [], itertools.count()


def add(priority, task):
    heapq.heappush(queue, (priority, next(counter), task))


add(2, {"name": "backup"})
add(1, {"name": "deploy"})
add(2, {"name": "report"})       # equal priority, yet dicts are never compared
while queue:
    p, _, task = heapq.heappop(queue)
    print(p, task["name"])       # 1 deploy, 2 backup, 2 report

scores = [5, 1, 9, 3]
max_heap = [-s for s in scores]   # flip the sign to use it as a max-heap
heapq.heapify(max_heap)
print(-max_heap[0], heapq.nlargest(2, scores))  # 9 [9, 5]

A heap does not support changing the priority of, or removing, an arbitrary element. The standard workaround is lazy deletion: push a new entry, mark the old one as stale, and skip stale entries when they are popped. The familiar line if d > dist[u]: continue in Dijkstra's algorithm is exactly this technique.

Pitfalls with C++ priority_queue

std::priority_queue is a max-heap by default. Pass std::greater as the third template argument for a min-heap. top() and pop() are separate calls, and calling either on an empty queue is undefined behaviour, so check empty() first.

#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>

int main() {
    std::priority_queue<int> maxq;  // max-heap
    std::priority_queue<int, std::vector<int>, std::greater<int>> minq;  // min-heap
    for (int x : {5, 1, 9, 3}) { maxq.push(x); minq.push(x); }
    std::cout << maxq.top() << ' ' << minq.top() << '\n';  // 9 1

    using Item = std::pair<int, std::string>;  // (distance, name) uses pair ordering
    std::priority_queue<Item, std::vector<Item>, std::greater<Item>> pq;
    pq.push({7, "b"});
    pq.push({3, "a"});
    std::cout << pq.top().second << '\n';  // a
}

Pitfalls with Java PriorityQueue

PriorityQueue is a min-heap by default; a Comparator changes the order. A comparator written as subtraction, (a, b) -> a - b, overflows for large values, so use Integer.compare or Comparator.comparingInt. Iterating with for or printing with toString() shows the internal array order, not sorted order; to see items in order, take them out with poll().

import java.util.Comparator;
import java.util.PriorityQueue;

public class Tasks {
    record Task(String name, int priority) {}

    public static void main(String[] args) {
        PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());
        max.addAll(java.util.List.of(5, 1, 9, 3));
        System.out.println(max.peek()); // 9

        PriorityQueue<Task> pq = new PriorityQueue<>(Comparator.comparingInt(Task::priority));
        pq.add(new Task("backup", 2));
        pq.add(new Task("deploy", 1));
        while (!pq.isEmpty()) System.out.println(pq.poll().name()); // deploy, backup
    }
}

Summary

Trees form the backbone of file systems, database indexes, sorted maps and schedulers, while heaps are the basic tool for timers, graph algorithms and top-K computations. When using a standard library, keep in mind its default order (min-heap in Python and Java, max-heap in C++), how ties are handled, and lazy deletion for priority changes, and you will avoid most pitfalls.