Same tree shape, different promises
Picture
A binary search tree promises an ordering across subtrees. A min-heap promises that every parent is no larger than its children. Those are different guarantees, so they support different operations. Choose the structure by the question you repeatedly ask, not by its drawing.
Predict
If a min-heap’s root is 2, can you decide whether 17 exists by comparing 17 to the root and exploring only one child?
Reveal the reasoning
No. Both child subtrees may contain values above 2, and either could contain 17. Heap ordering exposes a minimum; it does not divide all values into a smaller side and a larger side.
Go deeper: match the operation to the invariant
In a strict BST, every value in the left subtree is smaller than the node, and every value in the right subtree is larger. This is stronger than checking only immediate children. With search-tree height h, lookup takes O(h). Balancing can keep h=O(log n); ordinary insertion does not guarantee balance.
A binary heap maintains a complete tree shape, commonly stored in a list. In a min-heap, the smallest value is at index zero. Repeatedly selecting the cheapest pending task is exactly its strength.
from heapq import heappop, heappush
pending = []
for cost in [8, 2, 7, 1]:
heappush(pending, cost)
assert pending[0] == 1
assert [heappop(pending) for _ in range(4)] == [1, 2, 7, 8]
Push and pop cost O(log n); reading the minimum is O(1). A heap’s list is not fully sorted. Finding an arbitrary value can require O(n) inspection.
Need repeated exact membership with hashable keys? A set is often the simpler fit, with expected constant-time operations under usual hashing assumptions. Need prefix completions? A trie preserves a different relationship again.
Analogy limit: “tree” specifies relationships, not an operation’s speed. Ordering rules, shape guarantees, and representation determine what work can be avoided.
Change one rule
Instead of repeatedly extracting the cheapest task, you need one sorted list of all tasks and will never insert another. Is a heap mandatory?
Check the variation
No. Sorting once directly answers that workload. A heap becomes especially useful when selection and insertion are interleaved.
Connect
Dijkstra needs a cheapest-first frontier. Tries organize shared prefixes. Each structure stores the relationship that its repeated query can exploit.