Trees, Heaps, and Queues: Ordered Structures

A hash map answers "does it exist?" — a tree answers "where does it fit in order?" The ordered structures handle the questions hash maps can't: ranges, top-K, sorted iteration.

Heaps: the priority queue

import heapq
pq = []
heapq.heappush(pq, (priority, task))
priority, task = heapq.heappop(pq)   # always the lowest-priority item — O(log n)

Top-K problems (k largest in a stream), schedulers ("run the most important task next"), and merge-K-sorted-lists are all heap problems. The heap guarantees the min (or max) is at the top in O(1), and inserts/extracts in O(log n).

Binary search trees

Balanced BSTs (AVL, red-black — Postgres's B-tree is a multi-way version) give ordered iteration, range queries (WHERE x BETWEEN a AND b), and O(log n) lookup. A self-balancing BST is what powers every ordered index in every database.

Queues and stacks

• Queue (FIFO) — task queues, BFS, breadth-first processing. collections.deque for O(1) append/popleft.
• Stack (LIFO) — parsing, DFS, undo history, "matching brackets" — anything nested or last-in-first-out.

Field notes

• A heap for top-K is O(n log k) — if k << n, it beats sorting the whole thing (O(n log n)).
• Binary search on a sorted array is O(log n) — the array doesn't need to be a tree; the search itself is the algorithm.
• The choice isn't "which structure is fastest" — it's "which structure answers the questions I actually ask.