← Back to Index

🔺 Heap Pattern

🧠 When to Use

• Find Kth smallest/largest elements
• Maintain a dynamic top-K list
• Merge multiple sorted arrays/lists
• Continuously track min/max while streaming
• Scheduling problems or cost optimization

⚙️ Java Syntax

// Min-heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

📌 Common Techniques

• poll() – removes and returns top (min or max)
• offer(val) – adds a new element
• Use minHeap when you want the smallest item at top
• Use maxHeap to keep largest at top (e.g., for Kth smallest)

🔥 Popular Problems

• 347. Top K Frequent Elements [Medium] Heap
• 23. Merge k Sorted Lists [Hard] Heap
• 295. Find Median from Data Stream [Hard] Two Heaps
• 480. Sliding Window Median [Hard] Two Heaps
• 2402. Meeting Rooms III [Medium] Heap
• 2231. Largest Number After Digit Swaps by Parity [Easy] Sorting
• 436. Find Right Interval [Medium] TreeMap
• 1405. Longest Happy String [Medium] Max Heap
• 1792. Maximum Average Pass Ratio [Medium] Max Heap
• 1942. The Number of the Smallest Unoccupied Chair [Medium] Min Heap
• 1167. Minimum Cost to Connect Sticks [Medium] Heap
• 502. IPO [Hard] Heap
• Schedule Tasks on Minimum Machines [Medium] Heap

📊 Time Complexity

• offer(): O(log n)
• poll(): O(log n)
• peek(): O(1)

🧠 Pro Tips

• Use max-heap when you need to discard smaller elements
• Use a custom comparator for complex objects
• Always track heap size if using for top-K