Topic 59 of 78
Max-Heap
Overview
A Max-Heap is exactly the same as a Min-Heap, except the rule is reversed: every parent node must be LARGER than its children. This guarantees that the absolute maximum element is always instantly accessible at the root. It is used when you need to constantly retrieve the highest priority item, like triage in an emergency room or scheduling high-priority CPU tasks.
Syntax
Using `Collections.reverseOrder()` tells Java to flip the comparison logic.
Creating a Max-Heap
java
// Java's PriorityQueue is a Min-Heap by default.
// To make it a Max-Heap, you must reverse the natural ordering.
Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(10);
maxHeap.offer(50);
maxHeap.offer(20);
System.out.println(maxHeap.poll()); // Prints 50
System.out.println(maxHeap.poll()); // Prints 20Common Pitfalls
- Forgetting to provide a custom Comparator. If you don't, Java defaults to a Min-Heap, causing your highest-priority items to be processed last.
- Trying to search for a specific element in a Heap. Lookups are O(N) because a Heap is not a Binary Search Tree.
Interview Tips
- To find the K smallest elements in a massive stream of data, keep a Max-Heap of size K. When the heap exceeds K, pop the max. You are left with the K smallest elements.
Real-World Example
Operating Systems use Max-Heaps for CPU task scheduling. A task with priority 99 will automatically rise to the root of the heap and be executed before a task with priority 10.
example
java
Queue<Task> cpuQueue = new PriorityQueue<>((t1, t2) -> t2.priority - t1.priority);
cpuQueue.offer(new Task("Background Update", 1));
cpuQueue.offer(new Task("User Click", 100)); // Will be executed instantly