PriorityQueue and Binary Heaps

Master heap-based priority queues for task scheduling, top-K problems, and priority-based processing. Understand the binary heap implementation, heap operations, and when PriorityQueue outshines sorted collections.

📋 At a Glance

🎯 What You'll Learn

After completing this article, you will be able to:

1. Understand binary heap structure and operations
2. Use PriorityQueue for priority-based processing
3. Solve Top-K problems efficiently with heaps
4. Implement custom priority ordering with Comparators
5. Avoid common PriorityQueue pitfalls

Interactive Visualizer

Explore how binary heap maintains the min-heap property - watch siftUp during offer() and siftDown during poll():

Loading visualizer...

---

Production Story: The Job Scheduler That Played Favorites

The Incident

Our job scheduler was supposed to process high-priority jobs first. Instead, jobs were being processed in seemingly random order, causing SLA violations for critical tasks.

JAVA(14 lines)
Code
Loading syntax highlighter...

The Performance Problem

JAVA(8 lines)
Code
Loading syntax highlighter...

The PriorityQueue Solution

JAVA(21 lines)
Code
Loading syntax highlighter...

Why PriorityQueue Works

TEXT(18 lines)
Code
Loading syntax highlighter...

Lessons Learned

1. Don't re-sort for each insertion - use PriorityQueue
2. Heap operations are O(log n) - much better than O(n log n) sort
3. PriorityQueue is min-heap by default - reverse comparator for max-heap
4. Consider PriorityQueue for any priority-based processing

---

Mental Model: The Hospital Triage System

TEXT(24 lines)
Code
Loading syntax highlighter...

---

Deep Dive: Binary Heap Fundamentals

Heap Properties

JAVA(21 lines)
Code
Loading syntax highlighter...

Sift Up (after insertion)

JAVA(18 lines)
Code
Loading syntax highlighter...

Sift Down (after removal)

JAVA(14 lines)
Code
Loading syntax highlighter...

---

Deep Dive: PriorityQueue API

Construction

JAVA(20 lines)
Code
Loading syntax highlighter...

Basic Operations

JAVA(23 lines)
Code
Loading syntax highlighter...

Iteration Warning

JAVA(17 lines)
Code
Loading syntax highlighter...

---

Deep Dive: Common Patterns

Pattern 1: Top-K Elements

JAVA(34 lines)
Code
Loading syntax highlighter...

Pattern 2: Merge K Sorted Lists

JAVA(28 lines)
Code
Loading syntax highlighter...

Pattern 3: Streaming Median

JAVA(26 lines)
Code
Loading syntax highlighter...

Pattern 4: Task Scheduler with Cooldown

JAVA(33 lines)
Code
Loading syntax highlighter...

Pattern 5: K Closest Points

JAVA(19 lines)
Code
Loading syntax highlighter...

---

Deep Dive: PriorityQueue vs Alternatives

PriorityQueue vs TreeSet

JAVA(17 lines)
Code
Loading syntax highlighter...

PriorityQueue vs Sorted List

JAVA(14 lines)
Code
Loading syntax highlighter...

Performance Comparison

*O(1) if removing from end, O(n) from beginning **With binary search

---

⚠️ Common Mistakes

Mistake 1: Expecting Sorted Iteration

JAVA(11 lines)
Code
Loading syntax highlighter...

Mistake 2: Modifying Elements After Adding

JAVA(20 lines)
Code
Loading syntax highlighter...

Mistake 3: Using contains() Frequently

JAVA(18 lines)
Code
Loading syntax highlighter...

Mistake 4: Wrong Comparator Direction

JAVA(9 lines)
Code
Loading syntax highlighter...

Mistake 5: Null Elements

JAVA(10 lines)
Code
Loading syntax highlighter...

---

🐛 Debug This

Challenge 1: The Wrong Order

JAVA(12 lines)
Code
Loading syntax highlighter...

The heap orders by first element (a[0]), so:

• poll() returns {1, 200}, sum = 200
• poll() returns {2, 300}, sum = 500
• poll() returns {3, 100}, sum = 600

All elements are summed regardless of order.

Challenge 2: The Missing Update

JAVA(10 lines)
Code
Loading syntax highlighter...

Output:

TEXT(2 lines)
Code
Loading syntax highlighter...

Creating ArrayList from PriorityQueue copies elements in heap order (not sorted), then sort() sorts the list. PriorityQueue still works correctly, poll() returns minimum 3.

Challenge 3: The Comparator Confusion

JAVA(12 lines)
Code
Loading syntax highlighter...

Orders by string length (ascending): "c" (1), "bb" (2), "aaa" (3)

---

💻 Exercises

Exercise 1: Kth Largest Element

Find the kth largest element in an array:

JAVA(2 lines)
Code
Loading syntax highlighter...

JAVA(13 lines)
Code
Loading syntax highlighter...

Exercise 2: Top K Frequent Elements

Find k most frequent elements:

JAVA(2 lines)
Code
Loading syntax highlighter...

JAVA(23 lines)
Code
Loading syntax highlighter...

Exercise 3: Reorganize String

Rearrange string so no two adjacent chars are same:

JAVA(3 lines)
Code
Loading syntax highlighter...

JAVA(37 lines)
Code
Loading syntax highlighter...

Exercise 4: Meeting Rooms II

Find minimum meeting rooms required:

JAVA(2 lines)
Code
Loading syntax highlighter...

JAVA(19 lines)
Code
Loading syntax highlighter...

Exercise 5: Ugly Number II

Find nth ugly number (factors only 2, 3, 5):

JAVA(2 lines)
Code
Loading syntax highlighter...

JAVA(23 lines)
Code
Loading syntax highlighter...

---

🎤 Senior-Level Interview Questions

Question 1: Heap vs Balanced BST

JAVA(8 lines)
Code
Loading syntax highlighter...

Question 2: Heap Operations Complexity

Two approaches:

1. Naive: offer() n times → O(n log n)

JAVA(3 lines)
Code
Loading syntax highlighter...

1. Heapify: O(n) - build from bottom up

JAVA(4 lines)
Code
Loading syntax highlighter...

Why O(n)? Half the nodes are leaves (no sift). Quarter sift 1 level. Eighth sift 2 levels. Sum: O(n).

PriorityQueue(Collection) uses heapify: O(n).

Question 3: Streaming Top-K

Use a min-heap of size K:

JAVA(10 lines)
Code
Loading syntax highlighter...

• Space: O(K)
• Add: O(log K)
• Get all K: O(K log K) if sorted needed

For top-K smallest, use max-heap instead.

Question 4: Two-Heap Pattern

Split elements into two halves:

• Max-heap: smaller half (root = largest of smaller)
• Min-heap: larger half (root = smallest of larger)

JAVA(17 lines)
Code
Loading syntax highlighter...

Question 5: Priority Queue vs Sorted List

Sorting wins when:

1. One-time access: Sort once, access all in order
2. Random access needed: Sorted array/list has O(1) access
3. Infrequent updates: Rebuilding is rare

Priority Queue wins when:

1. Streaming data: Elements arrive continuously
2. Only need min/max: Don't need full ordering
3. Frequent updates: Many add/remove operations

JAVA(11 lines)
Code
Loading syntax highlighter...

Question 6: Custom Object in PriorityQueue

JAVA(22 lines)
Code
Loading syntax highlighter...

---

📝 Summary & Key Takeaways

Binary Heap Properties

• Complete binary tree stored in array
• Parent at (i-1)/2, children at 2i+1 and 2i+2
• Min-heap: parent ≤ children (root is minimum)
• Max-heap: parent ≥ children (root is maximum)

PriorityQueue Operations

• offer()/poll(): O(log n)
• peek(): O(1)
• contains()/remove(Object): O(n) - avoid!
• Building from collection: O(n)

Common Patterns

• Top-K: Min-heap of size K for K largest
• Merge K Sorted: Heap of K list heads
• Streaming Median: Two heaps (max for smaller, min for larger)
• Task Scheduling: Max-heap by priority

Best Practices

• Use Comparator.reverseOrder() for max-heap
• Don't modify elements after adding
• Use HashSet alongside for O(1) contains
• Poll for sorted iteration (iterator is NOT sorted)

---

🏁 Conclusion

PriorityQueue is essential for any priority-based processing. Its O(log n) operations make it dramatically faster than sorted lists for dynamic data, while the heap structure provides elegant solutions to problems like top-K and streaming median.

Key takeaways:

1. PriorityQueue is a min-heap by default - use reversed comparator for max
2. Iterator is NOT sorted - poll() for priority order
3. O(n) contains - use HashSet alongside if needed
4. Don't modify elements after adding (heap doesn't know)
5. Top-K pattern: Use min-heap of size K for K largest elements

In the next article, we'll explore ConcurrentHashMap - the thread-safe map that powers concurrent Java applications without the performance penalties of synchronized collections.

---

📅 Review Schedule

To solidify your understanding, review this material:

• Tomorrow: Implement Top-K pattern from memory
• In 3 days: Practice streaming median problem
• In 1 week: Explain heap vs BST tradeoffs
• In 2 weeks: Review all common heap patterns

---