Max-Heap
Overview
A Max-Heap is the exact opposite of a Min-Heap. It is a Complete Binary Tree where every parent node is greater than or equal to its children. Therefore, the absolute largest element is always sitting instantly accessible at the root node.
Java's PriorityQueue is a Min-Heap by default. To create a Max-Heap in Java, you must provide a custom Comparator that reverses the natural sorting order (Collections.reverseOrder()).
Max-Heaps are crucial when you continuously need access to the highest-value item, such as processing the most critical bug in an issue tracker, or selecting the highest paying bid in an auction system.
Syntax
import java.util.PriorityQueue;
import java.util.Collections;
public class MaxHeapDemo {
public static void main(String[] args) {
// Reverse the natural integer ordering to create a Max-Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(10);
maxHeap.offer(99);
maxHeap.offer(5);
maxHeap.offer(42);
// The largest element is immediately available
System.out.println("Maximum: " + maxHeap.peek()); // 99
// Extracting elements in descending order
while (!maxHeap.isEmpty()) {
System.out.println("Extracted: " + maxHeap.poll());
}
// Output: 99, 42, 10, 5
}
}Common Pitfalls
- Forgetting the
Collections.reverseOrder()argument. If you omit it, you will accidentally build a Min-Heap. This is the #1 mistake when writing Max-Heap logic in interviews. - Custom Object Comparators. When building a Max-Heap for custom objects (e.g.,
PriorityQueue<Student>), your comparator must be(a, b) -> b.score - a.score. Reversing theaandbin the subtraction reverses the sorting logic to descending order. - Integer Overflow in Custom Comparators. Using subtraction
b.score - a.scoreis dangerous if the numbers are massive (can cause underflow/overflow errors). Always useInteger.compare(b.score, a.score)for safety.
Interview Questions
This sounds counter-intuitive! You use a Max-Heap of size K. Iterate through the array, pushing elements into the Max-Heap. If the heap size exceeds K, poll() (remove) the maximum element. Because you constantly throw away the largest elements, at the end of the array, the heap contains only the K smallest elements, and the root is the Kth smallest. Time: O(N log K).
HeapSort is an O(N log N) sorting algorithm. You insert all elements into a Max-Heap. Then, you repeatedly extract the maximum element and place it at the end of the array, working backwards. It is extremely memory efficient (O(1) auxiliary space) but generally slower in practice than QuickSort due to poor cache locality.
Real-World Example
A Hospital Emergency Room Triage system uses a Max-Heap. Patients are assigned a severity score from 1 (minor) to 10 (life-threatening). The doctors always need to treat the patient with the highest severity score first, regardless of when they arrived.
class Patient {
String name;
int severity; // 1 to 10
// constructor...
}
// Max-Heap: Compare p2 to p1 to reverse natural order
PriorityQueue<Patient> triage = new PriorityQueue<>(
(p1, p2) -> Integer.compare(p2.severity, p1.severity)
);
triage.offer(new Patient("Alice", 2));
triage.offer(new Patient("Bob", 9));
triage.offer(new Patient("Charlie", 5));
// Bob is treated first because 9 is the maximum severity
Patient nextToTreat = triage.poll();Check Your Knowledge
Test your understanding of Max-Heap with these quick questions.