Trees and heaps: BSTs, priority queues and range queries

Hash maps answer "is this key present" and nothing else. The moment a question involves order — the smallest, the next one up, everything in a range — you need a tree or a heap, and which one depends on whether you need the whole order or only the extreme.

Proposition 3.1

What a BST buys over a hash map

Ordered operations: find the smallest key above a value, iterate in sorted order, count everything in a range. All are $O(\log n)$ in a balanced tree and impossible in a hash map, which is exactly the trade for its constant-time lookup.

Holds when

An unbalanced BST degenerates to a list on sorted input — hence AVL, red-black and treaps.
In-order traversal yields sorted output, which is often the whole reason to use one.
An order book’s price levels are the canonical financial example, though a fixed tick grid lets an array beat it.

Proposition 3.2

Heaps

A binary heap keeps the minimum at the root with $O(\log n)$ insert and extract, stored as a flat array with no pointers at all. It gives you the extreme element cheaply and tells you nothing about the rest of the order, which is precisely the trade that makes it faster than a tree.

Holds when

Building a heap from $n$ items is $O(n)$ , not $O(n\log n)$ — the analysis is a standard interview follow-up.
Finding an arbitrary element is $O(n)$ ; use a tree if you need that.
Two heaps facing each other — a max-heap of the low half and a min-heap of the high — maintain a streaming median.

Figure 3.3 · The heap is ordered only from parent to child. Every parent is no larger than its children, so the minimum is at the root. Siblings and cousins have no sorted order: 12 sits left of 10. That weaker invariant is what makes insertion and removal fast.

Figure 3.4 · Three ways to take the top hundred of a million. Sorting solves a harder problem than the one asked. A heap of size

k

costs

n\log k

and quickselect is linear on average — and the reason to know all three is that only the heap works when the million arrives as a stream you cannot store.

Why a bounded heap beats sorting. To keep the largest $k$ of a stream, hold a *min*-heap of size $k$ : the root is the weakest survivor, so each new element is compared against it and either discarded or swapped in. The heap never grows past $k$ , so the space is $O(k)$ and each step costs $\log k$ rather than $\log n$ . Sorting would need every element in memory and $O(n\log n)$ time — and on a genuine stream it is not available at all. The counter-intuitive part is using a min-heap to track maxima, and it is the whole trick.

Trees and heaps: BSTs, priority queues and range queries

After this lesson you should be able to

What a BST buys over a hash map

Heaps

The rest of this lesson is in Premium