The model
A search tree organizes keys so comparisons guide a search toward one subtree. A heap instead guarantees only that each parent outranks its children, which is enough to retrieve an extreme element quickly but not to search arbitrarily for a key. The word “tree” alone does not define the operation costs.
A concrete walk-through
A balanced search tree keeps its height proportional to log n, supporting lookup and ordered traversal. A binary heap stores a nearly complete tree compactly in an array: the children of index i are computed from i. Insert and remove-top repair a path through the heap, while peek-top reads the root.
Costs and failure cases
An unbalanced search tree can degrade to a linked list when keys arrive in sorted order. A heap cannot replace a search tree when the application needs predecessor, range, or arbitrary-key lookup. Heaps are a strong fit for schedulers and top-k selection when repeated access to the current priority matters.
Check your understanding
You need to repeatedly process the earliest deadline and occasionally ask whether a particular task exists. Which structure would you use for each responsibility, and why might one structure not cover both?