cconnected.
Understand the pattern. Find your own way.Find your starting point
Your learning feed/Idea 46 of 218
Ideas this builds on
Trees46 / 218

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.