Trees and Heaps Solve Different Ordering Problems

A search tree and a heap are both drawn as trees. They solve different problems and keep different promises.

A binary search tree organizes keys so comparisons guide each search toward one subtree. A heap guarantees only that each parent outranks its children. That single guarantee exposes the extreme element immediately and nothing else.

Their costs differ because their invariants differ. This article shows both, with the numbers that separate them.

Search trees trade height for ordered access

A binary search tree places smaller keys left and larger keys right. Lookup, insert, and delete each walk one root-to-leaf path. The cost equals the height: the number of edges on the longest path.

Height is the whole story. A balanced tree of a million keys stands about 20 levels tall. Every operation costs about 20 comparisons. An unbalanced tree can degenerate into a chain, and every operation then costs O(n).

The classic trigger is sorted input. Feeding sorted keys into a plain search tree attaches each one as the right child of the last. The "tree" becomes a linked list. Restoring rows in order once slowed a production database a hundredfold through exactly this shape.

Balanced trees prevent the collapse with rotations. Red-black trees and AVL trees rearrange nodes on every update so height stays logarithmic. The maintenance costs extra writes but keeps every path short.

Ordered navigation is what the tree buys beyond lookup. In-order traversal visits keys sorted. Predecessor and successor queries walk to neighbors. Range scans start at a lower bound and stop at an upper one. B-trees generalize the same idea for disk: many keys per node mean one page fetch covers a whole level, which is why database indexes use B-trees.

The same ordered map in three languages:

#include <map>
#include <string>
// An ordered map: keys stay sorted, lookups cost O(log n).
void demo() {
    // Red-black tree: insert three pairs in scrambled order.
    std::map<int, std::string> m;
    m[3] = "c"; m[1] = "a"; m[2] = "b";
    // Iteration visits keys sorted: 1, 2, 3.
    for (auto& [k, v] : m) { /* k arrives in order */ }
    // Range queries come free: first key not less than 2.
    auto it = m.lower_bound(2); // points at key 2
}

All three keep keys ordered and find bounds with binary search. The C++ and Java versions balance a real tree. The Python version shows the same contract over a sorted list.

Heaps keep the extreme on top and little else

A heap is a nearly complete binary tree stored in a plain array. No pointers exist. The children of index i sit at 2 × i + 1 and 2 × i + 2. The parent sits at (i − 1) / 2.

The heap invariant says each parent outranks its children. In a max-heap every parent is greater than or equal to its children. Nothing is claimed about siblings or cousins.

That single rule puts the maximum at index 0. Reading it costs O(1). Insertion appends at the end and walks the new element up until the invariant holds. Removing the top moves the last element to the root and walks it down. Both walks travel at most the height, so both cost O(log n).

Building a heap one insert at a time costs O(n log n). Floyd's bottom-up method sinks each subtree starting from the last parent and finishes in O(n). Standard libraries use the linear build for that reason.

The same priority queue in three languages:

#include <queue>
#include <vector>
// A max-heap: the largest element is always on top.
// Push and pop cost O(log n); reading the top costs O(1).
void demo() {
    // Vector-backed heap holding 5, 1, 9.
    std::priority_queue<int> q;
    q.push(5); q.push(1); q.push(9); // each push sifts up: O(log n)
    int top = q.top(); // 9: the extreme sits at index 0
    q.pop(); // remove 9, then sift the last element down: O(log n)
}

The C++ and Java versions expose a max-heap directly. Python ships a min-heap, so the top holds 1 instead of 9. The costs match in all three.

Why a heap cannot replace a search tree

Relaxing the order below the root removes the ability to search. No comparison tells you which subtree holds key 4821, because siblings carry no ordering promise. Finding an arbitrary key scans the whole array at O(n).

A heap answers one question: what is the current extreme. A search tree answers many questions about arbitrary keys. Neither covers the other without extra machinery.

Systems that need both usually combine structures. A task scheduler pairs a heap for "most urgent next" with a map from task ID to position. Canceling by ID updates the map, and the heap adjusts around it.

Where each structure runs and what to read next

Schedulers, event loops, and Dijkstra's frontier use heaps. They repeatedly need the extreme and nothing else. A million pending timers resolve each tick in about 20 heap steps.

Indexes, ordered maps, and range scans use search trees. They need arbitrary keys plus sorted order. A million-row table finds any key in about 20 tree steps and scans ranges sequentially.

Disk changes the winner. Pointers scatter across pages, so databases widen each node into hundreds of keys. One page fetch then covers a whole level of the B-tree.

Watch the trees and heaps trace to see both invariants execute. Follow the trees and heaps flow for the decision path. Then compare hash tables for the structure that trades order away for expected O(1) lookups.