Heap vs Binary Search Tree
A heap when you only ever want the smallest or largest item. A BST when you need to look up arbitrary values, iterate in order, or query ranges. A heap is a weaker structure, and that weakness is why it is cheaper.
Both are binary trees and the resemblance ends there. A heap only guarantees that a parent beats its children, so the minimum is at the root and everything else is unsorted. A BST guarantees a total ordering by position, so it can find any value. The heap's weaker promise is what lets it build in O(n) and sit in a flat array with no pointers at all.
Side by side
| Dimension | Heap | Binary Search Tree |
|---|---|---|
| Invariant | Parent beats both children | Left subtree smaller, right subtree larger |
| Find minimum | O(1), it is the root | O(log n), walk left |
| Find arbitrary value | O(n), no ordering to follow | O(log n) |
| Insert | O(log n) | O(log n) balanced |
| Delete the extreme | O(log n) | O(log n) |
| Sorted iteration | O(n log n), by draining it | O(n) in-order |
| Build from n items | O(n) | O(n log n) |
| Storage | A flat array, no pointers | Nodes with child references |
When to pick each
Heap
- Priority queues: task scheduling, Dijkstra, A star.
- Top k problems, where a heap of size k costs O(n log k).
- Streaming medians, using two heaps facing each other.
Binary Search Tree
- You look up values other than the extreme.
- You need sorted output, or a range, or the nearest key.
- You need to delete an arbitrary element, which a binary heap cannot do in O(log n) without extra indexing.
Expecting to remove an arbitrary element from a heap cheaply. Finding it is O(n) because a heap has no search order, so the usual workaround is lazy deletion: mark the element as removed and discard it when it surfaces at the top. This is exactly what a sliding-window median has to deal with, and it is a common follow-up question.
Questions people ask
Why is building a heap O(n) and not O(n log n)?
Because most nodes are near the bottom and sift down only a level or two. Summing the work by depth converges to a constant multiple of n, whereas inserting one at a time really is O(n log n).
Can a heap be stored without pointers?
Yes, and that is part of the appeal. In an array, node i has children at 2i+1 and 2i+2, so the structure is implicit and the memory is contiguous, which the cache likes.
Which does Java's PriorityQueue use?
A binary heap in an array. Note that iterating it does not give sorted order, which surprises people. Only repeated poll calls come out in order.