TreeMap, PriorityQueue, and Comparators

TreeMap, PriorityQueue, and Comparators

TreeMap Internals and Sorted Order

TreeMap in Java is a sorted map implementation based on a Red-Black tree, guaranteeing O(log n) worst-case time complexity for key operations such as put, get, and remove. This efficiency stems from the self-balancing properties of Red-Black trees: each node is colored red or black, the root is black, red nodes cannot have red children, and every path from the root to null has the same number of black nodes, ensuring height ≤ 2 log(n+1). Unlike HashMap, which provides average O(1) operations but no order, TreeMap maintains sorted key iteration via methods like keySet() or entrySet(), supporting range queries with O(log n) complexity through floorKey(K key), ceilingKey(K key), and subMap(K fromKey, K toKey). For instance, floorKey(K key) returns the greatest key less than or equal to the given key, or null if no such key, while ceilingKey(K key) returns the least key greater than or equal. TreeMap does not permit null keys when using natural ordering or a comparator, to preserve sorted integrity.

In practice, TreeMap excels in scenarios requiring sorted data, such as range queries or ordered traversal, at the cost of O(log n) per operation compared to HashMap’s O(1) average. This trade-off is explicit: TreeMap provides order with O(log n) time, whereas HashMap offers speed without order. The underlying memory layout involves each node storing key, value, color, and references to left child, right child, and parent, leading to O(n) space complexity. As detailed in the memory diagrams, TreeMap uses TreeNode objects with these fields, while PriorityQueue employs an array (Object[] queue) for heap order, with dynamic resizing doubling capacity when full for amortized O(1) time and O(n) space.

Java 21+ features enhance TreeMap usage with immutable data carriers. For example, using Records for keys ensures proper hashCode() and equals() implementations automatically, reducing verbosity. The following code demonstrates TreeMap with a custom comparator using a Record, showcasing sorted key iteration and floorKey operation:

import java.util.*;

public record Student(String name, int grade) {}

public class TreeMapExample {
    public static void main(String[] args) {
        // TreeMap with custom comparator using Record
        TreeMap<Student, String> map = new TreeMap<>(Comparator.comparing(Student::grade));
        map.put(new Student("Alice", 85), "A");
        map.put(new Student("Bob", 90), "B");
        System.out.println("Floor key for grade 88: " + map.floorKey(new Student("", 88)));
        // Time Complexity: O(log n) for put and floorKey, Space Complexity: O(n)
    }
}

This example highlights how custom comparators, via the Comparator interface requiring int compare(T o1, T o2) implementation, enable flexible ordering. Comparator consistency with equals is critical to avoid undefined behavior, as per Java specifications.

PriorityQueue and Heap-Based Operations

PriorityQueue in Java is an unbounded priority queue implemented as a binary heap, typically a min-heap by default. Its operations—offer(E e) for enqueue and poll() for dequeue—have O(log n) time complexity due to heap adjustments, while peek() offers O(1) time. The underlying structure is a complete binary tree where each parent node is less than or equal to its children in a min-heap, represented as an array with 0-based indexing: for index i, the parent is at (i-1)/2, left child at 2i+1, and right child at 2i+2. This array representation facilitates efficient siftUp and siftDown operations, with a default initial capacity of 11 and dynamic resizing for amortized O(1) time. Heapify can build a heap from an unsorted array in O(n) time using bottom-up construction, but full implementation details are reserved for advanced topics.

PriorityQueue is optimal for heap-based problems where incremental operations or top-K elements are needed, contrasting with sorting an entire array at O(n log n) cost. The trade-off is explicit: PriorityQueue provides efficient O(log n) per operation for heap tasks but lacks random access, making it unsuitable for scenarios requiring full sorting. Common applications include merging K sorted lists and finding top K frequent elements, both leveraging custom comparators for ordering.

For instance, merging K sorted lists uses a min-heap to achieve O(n log k) time complexity, where n is total elements and k is number of lists. The following code, using Java 21+ Records and pattern matching, demonstrates this:

import java.util.*;

public record ListNode(int val, ListNode next) {}

public class MergeKSortedLists {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.val()));
        for (ListNode node : lists) {
            if (node != null) pq.offer(node);
        }
        ListNode dummy = new ListNode(0, null);
        ListNode current = dummy;
        while (!pq.isEmpty()) {
            ListNode min = pq.poll();
            current.next(new ListNode(min.val(), null));
            current = current.next();
            if (min.next() != null) pq.offer(min.next());
        }
        return dummy.next();
        // Time Complexity: O(n log k) where n is total nodes, k is number of lists; Space Complexity: O(k) for heap
    }
}

Similarly, the top K frequent elements problem can be solved by combining HashMap for frequency counting and PriorityQueue with a custom comparator to maintain the top K elements. Here is a complete Java 21+ implementation:

import java.util.*;

public record ElementFrequency(String element, int count) {}

public class TopKFrequentElements {
    public List<String> topKFrequent(String[] elements, int k) {
        Map<String, Integer> frequencyMap = new HashMap<>();
        for (String element : elements) {
            frequencyMap.put(element, frequencyMap.getOrDefault(element, 0) + 1);
        }
        PriorityQueue<ElementFrequency> pq = new PriorityQueue<>(Comparator.comparingInt(ElementFrequency::count));
        for (Map.Entry<String, Integer> entry : frequencyMap.entrySet()) {
            pq.offer(new ElementFrequency(entry.getKey(), entry.getValue()));
            if (pq.size() > k) {
                pq.poll();
            }
        }
        List<String> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            result.add(pq.poll().element());
        }
        Collections.reverse(result); // To get descending order
        return result;
        // Time Complexity: O(n log k) where n is number of elements, Space Complexity: O(n) for map and heap
    }
}

This approach uses a min-heap to keep the K most frequent elements, with O(n log k) time and O(n) space, demonstrating PriorityQueue’s efficacy for top-K scenarios.

Practical Applications and Interview Patterns

In interviews, problems involving sorted order or heap operations require strategic data structure selection. TreeMap is ideal for range queries and sorted iteration, while PriorityQueue suits heap-based tasks like top-K elements or incremental sorting. The following complexity table compares key operations:

Data Structure	Operation	Average Time	Worst Time	Space Complexity
TreeMap	put/get/remove	O(log n)	O(log n)	O(n)
TreeMap	floorKey/ceilingKey	O(log n)	O(log n)	O(1) auxiliary
PriorityQueue	offer/poll	O(log n)	O(log n)	O(n)
PriorityQueue	peek	O(1)	O(1)	O(1)
HashMap	put/get	O(1)	O(n)	O(n)
Sorting array	sort	O(n log n)	O(n log n)	O(1) to O(n)

Trade-offs must be stated explicitly: TreeMap provides sorted keys at O(log n) time cost, HashMap offers fast lookups but no order, PriorityQueue enables efficient heap operations, and sorting arrays has a one-time O(n log n) overhead. The trade-off matrix below details these aspects:

Aspect	TreeMap	HashMap	PriorityQueue	Sorting Array
Order	Sorted keys	No order	Heap order (min/max)	Sorted after operation
Time Complexity	O(log n) operations	O(1) average, O(n) worst	O(log n) per operation	O(n log n) for full sort
Best Use Case	Range queries, sorted iteration	Fast lookups, no order needed	Heap problems, top-K elements	When entire dataset needs sorting
Trade-off	Provides order at cost of O(log n) time	Fast but unordered, memory overhead for collisions	Efficient for incremental ops but not for random access	One-time cost high, not incremental

Common failure modes include not handling null keys in TreeMap with comparators, incorrect comparator implementations breaking heap properties, assuming O(1) for all HashMap operations ignoring worst-case collisions, and using mutable keys in TreeMap that disrupt sorted order. The failure mode checklist enumerates these:

1. Not handling null keys in TreeMap when using natural ordering or comparator.
2. Incorrect comparator implementation leading to inconsistent ordering or broken heap properties in PriorityQueue.
3. Forgetting to override hashCode() and equals() for custom keys in maps, though Records handle this automatically.
4. Assuming O(1) performance for all HashMap operations without considering worst-case collisions.
5. Not analyzing space complexity for heap operations, especially in recursive or large-input scenarios.
6. Ignoring edge cases like empty lists in merge K sorted problems or negative values in heap operations.
7. Using mutable keys in TreeMap, which can break sorted order and cause undefined behavior.

A structured interview pattern guides problem-solving:

1. Understand problem: Identify if sorted order or heap operations are needed (e.g., range queries for TreeMap, top-K for PriorityQueue).
2. Choose data structure: Select TreeMap for sorted keys, PriorityQueue for heap-based problems, use custom comparator if required.
3. Implement with Java 21+ features: Use Records for immutable data carriers, sealed classes for closed hierarchies if applicable, pattern matching for exhaustive handling.
4. Analyze complexity: State time and space complexities with Big-O notation, considering worst-case scenarios (e.g., O(log n) for TreeMap, O(n log k) for merge K lists).
5. Test edge cases: Check null inputs, empty collections, duplicate keys, and concurrency issues if relevant.
6. State trade-offs: Explicitly compare with alternatives (e.g., TreeMap vs HashMap, PriorityQueue vs sorting).

By integrating these elements, developers can leverage TreeMap for sorted data management and PriorityQueue for efficient heap computations, ensuring robust, interview-ready solutions with clear performance guarantees.