Interview prompt
Explain trees and heaps solve different ordering problems to an engineer who understands the surrounding system but has not used this technique. Walk from its contract to a concrete operation, then discuss where it fails or becomes expensive.
A strong answer
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 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.
A complete answer also calls out the assumptions that control correctness. 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.
Close by describing one representative test or measurement. 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?
Follow-up questions
Answer the follow-ups in the frontmatter. Use the linked article for the concept and the trace to make the explanation concrete.