Section 2 of 5 · Algorithms & Data Structures
Search, Sorting, Trees & Heaps
Ordered structure turns brute force into logarithmic search, efficient selection and hierarchical state. The gain is reliable only when boundaries and representation invariants are explicit.
8 units 17 topics 0/8
Units
8 in this section
- 2.1 Sorting contracts, lower bounds and merge sort derive · implement5 h
- 2.2 Partitioning, quicksort, quickselect and top-k derive · implement5 h
- 2.3 Binary search: intervals, bounds and feasibility predicates derive · implement5 h
- 2.4 Tree representation and traversals implement4 h
- 2.5 Binary search trees, balance and augmented trees explain · implement5 h
- 2.6 Heaps and priority queues derive · implement4 h
- 2.7 Tries and prefix lookup implement3 h
- 2.8 Interval ordering, merging and sweep lines implement4 h
Before moving on
Checkpoint
Derive one binary-search boundary without patching it by examples, then solve one unseen tree and one heap or interval problem with adversarial tests and a worst-case defense.
Deliberately out of scope
Leave for later
- Implementing every balanced-tree variant
- External-memory and database index internals
- Advanced suffix trees and compressed indexes
Resources for this section
Shared by every unit above
- DSA Handbook - search, trees and heaps Study Part 2 Search and Sort, Part 5 Linked Lists, and Part 6 Trees and Heaps. Include canonical and answer-space binary search, comparison and linear-time sorts, quickselect, sentinels, cycles, heaps, BSTs, balanced-tree vocabulary, tries and segment trees.
- AlgoMaster DSA - ordered structures slice Attempt Koko Eating Bananas, Validate Binary Search Tree and Find Median from Data Stream cold. Use Merge Intervals only if interval modeling remains weak, and include duplicate-heavy and skewed inputs.
- Algorithmica - search and sorting performance Use the binary-search, sorting, branch prediction and cache chapters to explain why two algorithms with the same asymptotic bound cross over on real workloads.
- Algorithms Use Chapter 1 (mergesort, quicksort, recursion trees and linear-time selection) when deriving merge, partition and selection algorithms, and lecture note 12 Lower Bounds for the comparison-sorting decision-tree argument. This is the proof reference when the handbook explanation is too brief.
- NeetCode - unseen ordered problems Use one unseen tree problem and one heap or interval problem as the final transfer check, with solution material closed until submission.
- DSA Handbook Patterns - quicksort vs mergesort vs heapsort Use The decision, Algorithms compared and Side-by-side to pick a comparison sort from the binding constraint; problem details stay with their units.
- DSA Handbook Patterns - quickselect vs heap for top-K Use The decision through Side-by-side for the streaming, sorted-output and mutation routing; problem details stay with their units.
- DSA Handbook Patterns - two-heap median archetypes Use Streaming median and Variants side-by-side for the two-heap invariants; skip sliding-window median and sketches.
- DSA Handbook Patterns - merge intervals archetypes Use The decision, Variants and the LC 56 and LC 57 signature problems for merge and insert implementation, and the Meeting Rooms II archetype for the min-heap form.
- DSA Handbook Patterns - sweep line archetypes Use The decision and the 1D event sweep variant for
+1/-1concurrency counting with explicit tie-breaks; skyline and rectangle area are recognition only.
Apply the section
Mini-project · Mutable-priority heap, a derived boundary and a room scheduler (10 to 14 h)
Build an indexed heap with
update and remove, checked against a brute-force oracle. Derive one binary-search boundary from its predicate, then solve an unseen tree problem and a two-heap scheduling problem with adversarial tests and a worst-case defense.Steps
- Implement an indexed min-heap with
push,pop,peek,updateandremoveover a position map. State both invariants, heap order and index agreement, with the cost of each operation. - Test it with a Hypothesis state machine against a scanning oracle, checking both invariants after every step. Seed one defect, such as an
updatethat only sifts one way, and keep the shrunk history. - Solve LC 1011 Capacity To Ship Packages Within D Days with tags hidden. Write the feasibility predicate, prove it monotone and derive the bounds and updates from the loop invariant before running any example.
- Solve LC 236 Lowest Common Ancestor of a Binary Tree recursively, then add an iterative version with a parent map, since deep paths exceed the default recursion limit. Test both against an ancestor-set oracle on random trees.
- Solve LC 2402 Meeting Rooms III with two heaps, freeing rooms by number and busy rooms by end time. Write adversarial tests for delays, ties and back-to-back meetings, and compare against a brute-force simulator on small random inputs.
- Write the worst-case notes: the time bound for LC 2402, and why delayed end times overflow fixed-width integers, naming the largest end time the constraints allow.
Deliverables
- The indexed heap module with invariants, cost notes, the state machine and the seeded-defect history.
- The LC 1011 boundary derivation with the monotonicity proof, written before code.
- LC 236 and LC 2402 solutions with adversarial and differential tests and worst-case notes.
Checks
- rubric · Self-grade with the rubric below
- external-tests · LeetCode 1011: Capacity To Ship Packages Within D Days
- external-tests · LeetCode 236: Lowest Common Ancestor of a Binary Tree
- external-tests · LeetCode 2402: Meeting Rooms III
Rubric
| Criterion | Pass | Strong |
|---|---|---|
| Indexed heap | The state machine agrees with the oracle with both invariants checked after every step, and the seeded defect fails with a shrunk history. | Edge positions such as the root and the last slot are covered, with operation costs checked against the stated bounds. |
| Boundary derivation | The invariant and updates are written before any example runs, and the judge accepts the derived solution. | A property test checks the answer is the smallest feasible capacity: it holds, and one less fails. |
| Tree worst case | Both versions agree with the oracle, and the iterative version handles a deep path the recursive one cannot. | The write-up shows the recursive failure on the deep tree and states the space of each version. |
| Room scheduler | LC 2402 is accepted, and the simulator agrees on small random inputs with ties and back-to-back meetings. | The tie rules are stated as heap invariants, with the largest end time derived from the constraints. |
Feeds into: Capstone correctness library: the mutable-priority heap. Failure evidence: its seeded defect. The room scheduler is a first scheduler artifact for the milestone.