Integrated Data-Structure Reasoning

Composing Structures

Real problems rarely need a single structure — they combine several, each handling the part it makes fast. The art is decomposing a problem into sub-tasks and matching each to the right structure.

Consider a task manager that must: add tasks with priorities, always run the most urgent next, look up any task by id to update or cancel it, and list tasks in sorted deadline order. No one structure does all four well, so you compose:

• A heap (priority queue) to always extract the most urgent task in $O(\log n)$.
• A hash table mapping task id → task, for $O(1)$ lookup, update, and cancellation by id.
• A balanced BST keyed by deadline, to iterate tasks in deadline order and answer range queries ("due this week") in $O(\log n)$.

The structures cooperate: adding a task inserts it into all three; running the next task pops the heap and removes the entry from the others. The extra memory (three references to each task) buys fast operations across every access pattern the workload demands — a deliberate space–time trade-off.

This is the mature skill the unit builds toward: given a workload, identify the distinct access patterns, choose (or combine) structures so each is efficient, respect each structure's invariants, reason about the overall complexity, and test with edge cases (an empty manager, duplicate deadlines, cancelling a running task). Data structures are not isolated facts but a toolkit you compose.

Common pitfall: forcing a single data structure to serve a workload with several distinct access patterns, and paying $O(n)$ for the operations it does not support. When a problem needs fast keyed lookup and fast extreme-extraction and sorted iteration, the right answer is usually to combine structures — each doing what it is best at — not to compromise on one.