Heap vs Binary Search Tree: They're Both Trees. One of Them Can't Search.
- Heap enforces partial order (parent beats children only); siblings are unordered, so finding any non-root element costs O(n)
- Binary search tree enforces total order at every node, enabling O(log n) search, range queries, and sorted iteration
- Build time favors the heap: O(n) via Floyd's bottom-up algorithm vs O(n log n) for a balanced BST
- Memory favors the heap: ~4 bytes per element (array, no pointers) vs 32-40 bytes per BST node
- Use a heap for priority queues, top-k problems, Dijkstra's algorithm, and any workload that only asks for the minimum or maximum
- Use a BST when you need to find arbitrary elements, answer range queries, iterate in sorted order, or delete a specific value
You pick a heap. Your interviewer asks you to find a specific element. You spend the next thirty seconds explaining why you'd have to scan the whole thing. Wrong data structure, wrong moment, and now the interviewer is writing something down.
Both heaps and binary search trees are hierarchical. Both give you O(log n) insert. Both come up constantly in algorithm discussions. But they solve completely different problems, and swapping them is one of the more expensive mistakes you can make in an interview, because you don't find out until the follow-up question.
Use a heap when you only care about the minimum or maximum. Use a BST when you need to find, iterate, or range-query anything else. The rest of this article explains exactly why that line sits where it does.
The heap experience, nailed. Also, "aw fuck we gotta rehash ALRIGHT EVERYONE GET UP TIME TO MOVE THE FURNITURE" is just a perfect description of table resizing.
The Invariant Is Everything
A heap enforces one rule: every parent is greater than or equal to its children (max-heap), or less than or equal to them (min-heap). That's the complete specification. Siblings can be in any order relative to each other. The second-largest element could be anywhere.
A BST enforces a different rule: every node in the left subtree is smaller than the current node, and every node in the right subtree is larger. This applies at every level, all the way down.
The heap's partial order is enough to expose the maximum in O(1). It's not enough to locate anything else without a linear scan.
The BST's total order lets you find any element in O(log n), walk the tree in sorted order without extra cost, and answer range queries. Every comparison at each node tells you which half of the remaining data to eliminate. The heap comparison only tells you the parent beats the children. The siblings are a coin flip.
Three Numbers in This Table Have Surprised Every Engineer at Least Once
| Operation | Heap (min or max) | Balanced BST |
|---|---|---|
| Find min or max | O(1) | O(log n) |
| Insert | O(log n) | O(log n) |
| Delete min or max | O(log n) | O(log n) |
| Find arbitrary element | O(n) | O(log n) |
| Delete arbitrary element | O(n) find + O(log n) fix | O(log n) |
| Build from n elements | O(n) | O(n log n) |
| In-order (sorted) iteration | O(n log n) | O(n) |
| Range query [a, b] | O(n) | O(log n + k) |
| Memory per node | ~4 bytes (array, no pointers) | 24-40 bytes (value + left + right + parent) |
Three rows bite people. Heap build is O(n), not O(n log n). Heap sorted iteration costs O(n log n) because you pop one element at a time, which is basically just heap sort. And range queries on a heap degrade to a full scan, while a BST answers them in O(log n + k) where k is the number of results.
What a Heap Cannot Do (And This Comes Up Every Time)
Here is the heap problem in code. You have a min-heap. You want to check whether 37 exists.
import heapq nums = [42, 20, 37, 5, 15, 3, 10] heapq.heapify(nums) # nums is now a valid min-heap: [3, 5, 10, 20, 15, 42, 37] or similar found = 37 in nums # O(n) linear scan, identical to scanning a plain list
The heap doesn't know where 37 is. It knows 3 is at the root. It knows each parent beats its children. Beyond that, nothing. Python's heapq module doesn't expose a delete-by-value operation because doing so requires an O(n) search first, making the whole operation O(n) rather than the O(log n) people expect from a tree.
The same problem applies to "give me the k-th smallest overall," "delete this specific task," and "find everything between 20 and 50." All of these require a full scan on a heap. All of them are O(log n) or O(log n + k) on a balanced BST.
What a BST Costs You (It's Not Nothing)
The BST charges on two fronts: memory and build time.
Memory first. A heap is an array. The parent of the node at index i is at (i-1)//2. Left child at 2i+1, right at 2i+2. No pointers at all. For a million integers, that's roughly 4 MB of contiguous memory. Clean, sequential, cache-friendly.
A BST node carries a value, a left pointer, a right pointer, and typically a parent pointer. On a 64-bit system that's 32 to 40 bytes per node. The same million elements cost 32 to 40 MB. A balanced BST implementation (AVL or Red-Black) adds a height or color field, pushing that higher. The BST can use 8 to 10 times more memory than a heap holding the same data.
Build time next. Building a heap from n unsorted elements takes O(n) via Floyd's bottom-up algorithm. Building a balanced BST from unsorted data takes O(n log n), because each of the n insertions performs O(log n) comparison and rotation work.
If you are setting up a priority queue, you don't want to pay O(n log n) before your first pop. That's like paying for parking before deciding whether you want to go inside the restaurant.
Two Trees, Same Values
Both structures below hold the values 10, 15, 20, 25, 30, 35, 40.
Same seven values. Different invariants. The heap doesn't know where 20 is. The BST goes left, right, done.
In the max-heap, 15 sits to the right of 35 even though 15 is smaller. Legal: the heap only enforces parent-to-child ordering. In the BST, every node to the left of 25 is smaller than 25, every node to the right is larger, and this holds recursively.
Now search for 20. In the heap, you check: 40 (no), 30 (no), 35 (no), 25 (no), 20 (found, fifth probe). If 20 were absent, you'd visit all seven nodes. In the BST: 25 (go left), 15 (go right), 20 (found). Three probes, done.
Why Heap Build Is O(n) and Why Nobody Can Derive It Under Pressure
Most engineers know the fact. Few can sketch the proof. It comes from the shape of a complete binary tree.
Half the nodes are leaves. Leaves need zero work to satisfy the heap property. A quarter of the nodes sit one level above leaves and need at most one comparison to sift down. An eighth need at most two. The total work adds up as:
n/2 × 0 + n/4 × 1 + n/8 × 2 + n/16 × 3 + ...
= n × Σ(k / 2^k) for k = 0 to log n
= n × 2
= O(n)
The geometric series Σ(k/2^k) converges to 2. Half the nodes are leaves and they're free. That's the whole trick.
Building a heap is O(n) because the vast majority of nodes live near the bottom, where sifting is cheap or free.
The naive approach, inserting elements one by one, costs O(n log n). Floyd's insight is to start with a heap that may violate the property, then restore it level by level from the bottom. The expensive work happens near the root, where there are almost no nodes.
Cache Misses Are Real and Painful
Asymptotic analysis doesn't tell the whole story. For large datasets, cache behavior matters more than the constants suggest.
The heap is an array. Accessing a parent at index i and its children at 2i+1 and 2i+2 touches adjacent memory. Modern CPUs prefetch sequential cache lines automatically. You get the next few comparisons nearly for free.
BST nodes are allocated dynamically and scattered across memory. Each pointer dereference is a potential cache miss. For a BST with a million nodes, a search touching 20 nodes from root to leaf can trigger 20 separate cache misses, each costing 80 to 100 nanoseconds on a DRAM access. An L1 cache hit costs 2 nanoseconds. That's a 40-50x difference per probe.
Benchmarks comparing contiguous structures to std::set (a Red-Black tree) consistently show the BST paying significant overhead from pointer chasing. For workloads that only need priority queue operations, a heap is faster in practice, not just on paper.
One Question Settles It
Do you need the extreme value, or do you need to navigate the full set?
The answer is almost always obvious once you ask the right question.
Priority queue, task scheduling, Dijkstra's algorithm, top-k by polling: use a heap.
Search by value, sorted output, range queries, predecessor or successor, delete a specific element: use a balanced BST.
Three cases where it matters.
"Find the k-th largest in a stream." Maintain a min-heap of size k. When a new element arrives, push it and pop the minimum if the heap exceeds k. The heap's root is always the k-th largest. O(log k) per element, O(1) to read the answer. A BST would work too, but carries 8x the memory for no benefit.
"Find all log entries between timestamps 09:00 and 09:30." A BST keyed on timestamp lets you binary-search to the first entry in range and walk forward. O(log n + k). A heap forces you to scan every entry. O(n). At 10 million entries, that's the difference between microseconds and seconds.
"Run Dijkstra's on a large graph." You need the minimum-distance vertex at each step. A heap gives O(log V) extraction and insertion. The BST can also do this, but most language standard libraries provide heaps and not indexed BSTs. The heap wins on implementation cost.
The Short Version
- Heap: partial order, O(1) min/max, O(log n) insert and delete-min, O(n) build, array-backed, cache-friendly, 4 bytes per element.
- BST: total order, O(log n) everything, O(n log n) build, pointer-based, 32+ bytes per node.
- If you only ask "what is the minimum?", the BST is doing extra work you're not using.
- If you ever need to find an arbitrary element, the heap forces a full scan.
- Heap wins on memory and build time. BST wins on search, range queries, sorted iteration, and arbitrary deletion.
- Both give O(log n) insert. That's where the similarity ends.
Tradeoff questions like this show up constantly in voice-based technical screens, and the right answer sounds different out loud than it does in your head. SpaceComplexity runs realistic mock interviews where you reason through these choices under realistic time pressure, then get rubric-based feedback on whether your reasoning was clear enough to score.
For deeper coverage of each structure, see The Heap Data Structure and The Binary Search Tree. If the BST side of this comparison leads you to choose between AVL and Red-Black trees, AVL Tree vs Red-Black Tree covers where those differ.