PriorityQueue / Heap

📋 Quick Reference

---

🎮 Interactive Visualizer

Watch how the heap maintains its properties during insertions and extractions:

Loading visualizer...

1. Insert elements - see "bubble up" (heapify up)
2. Poll minimum - watch "bubble down" (heapify down)
3. Notice: parent ≤ children (min-heap property)
4. Peek - instant O(1) access to root

---

🔧 Key Operations

Creating

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

Adding

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

Accessing

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

Removing

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

Other Operations

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

---

📊 Complexity Analysis

Heap Structure

Array representation of min-heap:
Index:    0   1   2   3   4   5   6
Value:   [1] [3] [2] [7] [4] [5] [6]

Tree view:
           1          <- root (index 0)
         /   \
        3     2       <- level 1 (indices 1, 2)
       / \   / \
      7   4 5   6     <- level 2 (indices 3-6)

Parent of i: (i-1)/2
Left child: 2*i + 1
Right child: 2*i + 2

---

✅ When to Use PriorityQueue

Good Use Cases

• Task scheduling - process highest priority first
• K-smallest/largest - find top K elements
• Dijkstra's algorithm - next closest vertex
• Merge K sorted lists - next smallest element
• Median finding - two heaps approach

Avoid When

• Need all elements sorted - use TreeSet or sort array
• Frequent contains() checks - O(n) each time
• Need indexed access - no get(i) method
• Need to remove arbitrary elements - O(n) to find

---

🧩 Common Patterns

Top K Elements

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

K Closest Points

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

Merge K Sorted Lists

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

---

⚠️ Common Pitfalls

1. Assuming Sorted Iteration

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

2. Using contains() Frequently

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

3. Wrong Comparator for Max-Heap

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

4. Modifying Elements After Insert

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

---

🎤 Interview Tips

"

Use PriorityQueue with Comparator.reverseOrder() or a custom comparator that reverses the natural ordering. Example: new PriorityQueue<>(Collections.reverseOrder())

"

Use a min-heap of size k. Add all elements; if size exceeds k, poll the minimum. After processing, the heap root is the kth largest. Time: O(n log k).

"

While each sift-down is O(log n), most nodes are near the leaves where sift-down is cheap. Mathematical analysis shows the sum converges to O(n), not O(n log n).

"

PriorityQueue allows duplicates, is faster for just min/max operations, but iteration is unordered. TreeSet maintains sorted order, no duplicates, and supports range queries.

---

📚 Series Navigation

---