Search trees and height
A binary search tree orders subtrees by a comparator: smaller keys left, larger keys right. Search follows a single downward path. Its cost depends on height, not merely the number of nodes: sorted insertion can create a chain in an ordinary unbalanced tree. Balanced trees keep height logarithmic through structural maintenance. TreeMap is useful when floor, ceiling, sorted traversal or range operations are part of the workload.
A heap is only partially ordered
In a binary min-heap, every parent is no larger than its children. This makes the root a minimum, while leaving most pairs unrelated. Removing the root moves another element into its place and restores the invariant by sifting. Java PriorityQueue iteration is not sorted output. Bottom-up heap construction is linear because most nodes sit near the leaves and need little work; repeated insertion is a different procedure.
Tries share prefixes
A trie follows symbols along edges, so words with a common prefix share a path. Reaching a prefix of length p can take O(p) steps with suitable child access, but returning suggestions also visits output nodes. Fixed-size child arrays trade memory for direct access; sparse maps reduce unused children but introduce hashing or comparison costs. Unicode and normalization policies must be defined before treating every Java char as one user-visible character.
Worked Java example
Illustrative snippet: imports, surrounding types or collaborators may be omitted. Read the assumptions before adapting it.
PriorityQueue<Integer> top = new PriorityQueue<>();
for (int value : values) {
top.offer(value);
if (top.size() > k) top.poll();
}
// With k > 0, top.peek() is the kth largest after all input.Walkthrough
For [4, 1, 7, 3] and k = 2, the heap keeps [1, 4], then inserts 7 and discards 1, then inserts 3 and discards 3. It retains the largest two values, 4 and 7; its root is 4. Do not treat heap iteration as the sorted sequence [4, 7]. Validate k and decide what to return when fewer than k values exist.
Practice it yourself
Compare a heap and a TreeMap for a service that repeatedly asks for the cheapest price at or above a threshold.
Check your reasoning
A heap cheaply exposes the global minimum but not arbitrary successor queries. An ordered map supports ceilingEntry in logarithmic time. Keep duplicate prices through counts or lists rather than losing products with equal prices.
Recall checklist
- Explain the main invariant or contract without looking.
- Trace the example and test an edge case.
- State time, space, input variables and assumptions where relevant.
- Explain one alternative and when you would choose it.