[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":94,"_72":95,"_35":96},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":52,"_64":65,"_66":67,"_68":69,"_70":71},"id",113,"title","PriorityQueue and Binary Heaps","slug","java-collections-part-17-priorityqueue-heap","excerpt","Understand binary heap implementation for priority-based processing, PriorityQueue's O(log n) operations, Top-K problems, and task scheduling patterns.","# Java Collections Compendium Part 17: PriorityQueue & Heap Operations\n\nMaster 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.\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| **Topic** | PriorityQueue, Binary Heap, Priority-based processing |\n| **Complexity** | Intermediate to Advanced |\n| **Prerequisites** | Part 16 (Queue/Deque) |\n| **Time to Master** | 3-4 hours |\n| **Interview Frequency** | Very High (Top-K, scheduling, heap operations) |\n\n## 🎯 What You'll Learn\n\nAfter completing this article, you will be able to:\n\n1. Understand binary heap structure and operations\n2. Use PriorityQueue for priority-based processing\n3. Solve Top-K problems efficiently with heaps\n4. Implement custom priority ordering with Comparators\n5. Avoid common PriorityQueue pitfalls\n\n### Interactive Visualizer\n\nExplore how binary heap maintains the min-heap property - watch siftUp during offer() and siftDown during poll():\n\n```visualizer-priorityqueue\ncontrols: true\n```\n\n---\n\n## Production Story: The Job Scheduler That Played Favorites\n\n### The Incident\n\nOur 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.\n\n```java\n// JobScheduler.java - The buggy code\npublic class JobScheduler {\n private List jobQueue = new ArrayList<>();\n\n public void submit(Job job) {\n jobQueue.add(job);\n Collections.sort(jobQueue, Comparator.comparingInt(Job::getPriority));\n }\n\n public Job getNextJob() {\n if (jobQueue.isEmpty()) return null;\n return jobQueue.remove(0); // Get highest priority\n }\n}\n```\n\n### The Performance Problem\n\n```java\n// With 10,000 pending jobs:\n// submit() → O(n log n) for each job added!\n// Total for n jobs: O(n² log n)\n\n// Timeline:\n// 1000 jobs: 50ms\n// 5000 jobs: 1.2 seconds\n// 10000 jobs: 5+ seconds per submission!\n```\n\n### The PriorityQueue Solution\n\n```java\n// JobScheduler.java - The efficient solution\npublic class JobScheduler {\n private PriorityQueue jobQueue = new PriorityQueue<>(\n Comparator.comparingInt(Job::getPriority).reversed() // Max priority first\n );\n\n public void submit(Job job) {\n jobQueue.offer(job); // O(log n)\n }\n\n public Job getNextJob() {\n return jobQueue.poll(); // O(log n)\n }\n}\n\n// With 10,000 pending jobs:\n// submit() → O(log n) ≈ 14 comparisons\n// Total for n jobs: O(n log n)\n\n// Timeline:\n// 10000 jobs: ~10ms (500x faster!)\n```\n\n### Why PriorityQueue Works\n\n```text\nBinary Heap Structure (min-heap by default):\n\n [1] Level 0 (root = minimum)\n / \\\n [3] [2] Level 1\n / \\ / \\\n [7] [4] [5] [6] Level 2\n\nArray representation: [1, 3, 2, 7, 4, 5, 6]\n\nParent of i: (i-1) / 2\nLeft child: 2*i + 1\nRight child: 2*i + 2\n\nOperations:\n• offer(x): Add at end, sift up → O(log n)\n• poll(): Remove root, move last to root, sift down → O(log n)\n• peek(): Return root → O(1)\n```\n\n### Lessons Learned\n\n1. **Don't re-sort for each insertion** - use PriorityQueue\n2. **Heap operations are O(log n)** - much better than O(n log n) sort\n3. **PriorityQueue is min-heap by default** - reverse comparator for max-heap\n4. **Consider PriorityQueue for any priority-based processing**\n\n---\n\n## Mental Model: The Hospital Triage System\n\n```text\n┌─────────────────────────────────────────────────────────────────────┐\n│ HOSPITAL TRIAGE (PRIORITY QUEUE) │\n├─────────────────────────────────────────────────────────────────────┤\n│ │\n│ Waiting Room (sorted list approach - inefficient): │\n│ ┌─────────────────────────────────────────────────────────────┐ │\n│ │ [P1] [P1] [P2] [P2] [P2] [P3] [P3] [P3] [P3] [P3] │ │\n│ └─────────────────────────────────────────────────────────────┘ │\n│ New patient → find position → shift everyone → O(n) │\n│ │\n│ Triage Heap (PriorityQueue - efficient): │\n│ │\n│ [P1-Critical] │\n│ / \\ │\n│ [P2-Urgent] [P1-Critical] │\n│ / \\ / │\n│ [P3-Minor] [P2-Urgent] [P3-Minor] │\n│ │\n│ New patient → add at bottom → bubble up → O(log n) │\n│ Next patient → take root → reheapify → O(log n) │\n│ │\n│ Key insight: We only need the HIGHEST priority, not full sorting! │\n│ │\n└─────────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## Deep Dive: Binary Heap Fundamentals\n\n### Heap Properties\n\n```java\n// Min-Heap Property:\n// Every parent is ≤ its children\n// Root is always the minimum\n\n// Array representation of heap:\n// For element at index i:\n// - Parent: (i - 1) / 2\n// - Left child: 2 * i + 1\n// - Right child: 2 * i + 2\n\n// Example: [1, 3, 2, 7, 4, 5, 6]\n//\n// Index: 0 1 2 3 4 5 6\n// Value: 1 3 2 7 4 5 6\n//\n// Tree view:\n// 1 (index 0)\n// / \\\n// 3 2 (indices 1, 2)\n// / \\ / \\\n// 7 4 5 6 (indices 3, 4, 5, 6)\n```\n\n### Sift Up (after insertion)\n\n```java\n// Adding element 0 to heap [1, 3, 2, 7, 4, 5, 6]:\n\n// Step 1: Add at end\n// [1, 3, 2, 7, 4, 5, 6, 0]\n\n// Step 2: Compare with parent (index 3, value 7)\n// 0 < 7, swap\n// [1, 3, 2, 0, 4, 5, 6, 7]\n\n// Step 3: Compare with parent (index 1, value 3)\n// 0 < 3, swap\n// [1, 0, 2, 3, 4, 5, 6, 7]\n\n// Step 4: Compare with parent (index 0, value 1)\n// 0 < 1, swap\n// [0, 1, 2, 3, 4, 5, 6, 7]\n\n// Done! New minimum is at root\n```\n\n### Sift Down (after removal)\n\n```java\n// Removing root from heap [1, 3, 2, 7, 4, 5, 6]:\n\n// Step 1: Replace root with last element\n// [6, 3, 2, 7, 4, 5]\n\n// Step 2: Compare with children (3 and 2)\n// 6 > 2 (smaller child), swap\n// [2, 3, 6, 7, 4, 5]\n\n// Step 3: Compare with children (5 only, 6 is at index 2)\n// 6 > 5, swap\n// [2, 3, 5, 7, 4, 6]\n\n// Done! Heap property restored\n```\n\n---\n\n## Deep Dive: PriorityQueue API\n\n### Construction\n\n```java\n// Default: min-heap with natural ordering\nPriorityQueue minHeap = new PriorityQueue<>();\n\n// Initial capacity\nPriorityQueue sized = new PriorityQueue<>(100);\n\n// Custom comparator: max-heap\nPriorityQueue maxHeap = new PriorityQueue<>(Comparator.reverseOrder());\n\n// Complex ordering\nPriorityQueue taskQueue = new PriorityQueue<>(\n Comparator.comparingInt(Task::getPriority)\n .reversed() // Higher priority first\n .thenComparing(Task::getCreatedAt) // Earlier tasks first\n);\n\n// From collection\nList list = Arrays.asList(5, 2, 8, 1, 9);\nPriorityQueue fromList = new PriorityQueue<>(list);\n// Heapified: [1, 2, 8, 5, 9]\n```\n\n### Basic Operations\n\n```java\nPriorityQueue pq = new PriorityQueue<>();\n\n// Add elements - O(log n)\npq.offer(5); // Returns true (always for PriorityQueue)\npq.add(3); // Same as offer, throws if would violate capacity\n\n// Peek at head - O(1)\nInteger min = pq.peek(); // Returns 3, doesn't remove\nInteger elem = pq.element(); // Same, throws if empty\n\n// Remove head - O(log n)\nInteger removed = pq.poll(); // Returns 3, removes it\nInteger rem2 = pq.remove(); // Same, throws if empty\n\n// Size and empty check\nint size = pq.size();\nboolean empty = pq.isEmpty();\n\n// Contains - O(n)! No fast lookup\nboolean has5 = pq.contains(5); // Linear search\n\n// Remove specific element - O(n)\npq.remove(5); // Finds and removes 5 (not head)\n```\n\n### Iteration Warning\n\n```java\nPriorityQueue pq = new PriorityQueue<>(Arrays.asList(5, 2, 8, 1, 9));\n\n// ⚠️ Iterator does NOT return elements in priority order!\nfor (Integer i : pq) {\n System.out.print(i + \" \"); // Might print: 1 2 8 5 9 (heap order, not sorted!)\n}\n\n// ✅ To get priority order, poll repeatedly:\nwhile (!pq.isEmpty()) {\n System.out.print(pq.poll() + \" \"); // Prints: 1 2 5 8 9\n}\n\n// ✅ Or convert to sorted list first:\nList sorted = new ArrayList<>();\nwhile (!pq.isEmpty()) {\n sorted.add(pq.poll());\n}\n```\n\n---\n\n## Deep Dive: Common Patterns\n\n### Pattern 1: Top-K Elements\n\n```java\n// Find K largest elements in O(n log k) time, O(k) space\npublic List topKLargest(int[] nums, int k) {\n // Min-heap of size k\n PriorityQueue minHeap = new PriorityQueue<>();\n\n for (int num : nums) {\n minHeap.offer(num);\n if (minHeap.size() > k) {\n minHeap.poll(); // Remove smallest\n }\n }\n\n return new ArrayList<>(minHeap);\n}\n\n// Why min-heap for largest?\n// We keep the k largest seen so far.\n// When new element comes:\n// - If smaller than min of k largest → ignore\n// - If larger → add and remove the smallest of k largest\n\n// Alternative: Max-heap for K smallest\npublic List topKSmallest(int[] nums, int k) {\n PriorityQueue maxHeap = new PriorityQueue<>(Comparator.reverseOrder());\n\n for (int num : nums) {\n maxHeap.offer(num);\n if (maxHeap.size() > k) {\n maxHeap.poll(); // Remove largest\n }\n }\n\n return new ArrayList<>(maxHeap);\n}\n```\n\n### Pattern 2: Merge K Sorted Lists\n\n```java\npublic ListNode mergeKLists(ListNode[] lists) {\n PriorityQueue pq = new PriorityQueue<>(\n Comparator.comparingInt(node -> node.val)\n );\n\n // Add first node of each list\n for (ListNode list : lists) {\n if (list != null) {\n pq.offer(list);\n }\n }\n\n ListNode dummy = new ListNode(0);\n ListNode current = dummy;\n\n while (!pq.isEmpty()) {\n ListNode smallest = pq.poll();\n current.next = smallest;\n current = current.next;\n\n if (smallest.next != null) {\n pq.offer(smallest.next);\n }\n }\n\n return dummy.next;\n}\n// Time: O(n log k) where n = total nodes, k = number of lists\n```\n\n### Pattern 3: Streaming Median\n\n```java\npublic class MedianFinder {\n // Max-heap for smaller half\n private PriorityQueue maxHeap = new PriorityQueue<>(Comparator.reverseOrder());\n // Min-heap for larger half\n private PriorityQueue minHeap = new PriorityQueue<>();\n\n public void addNum(int num) {\n // Add to max-heap first\n maxHeap.offer(num);\n\n // Balance: largest of smaller half should be ≤ smallest of larger half\n minHeap.offer(maxHeap.poll());\n\n // Keep sizes balanced (maxHeap can have one more)\n if (minHeap.size() > maxHeap.size()) {\n maxHeap.offer(minHeap.poll());\n }\n }\n\n public double findMedian() {\n if (maxHeap.size() > minHeap.size()) {\n return maxHeap.peek();\n }\n return (maxHeap.peek() + minHeap.peek()) / 2.0;\n }\n}\n```\n\n### Pattern 4: Task Scheduler with Cooldown\n\n```java\npublic int leastInterval(char[] tasks, int cooldown) {\n int[] counts = new int[26];\n for (char task : tasks) {\n counts[task - 'A']++;\n }\n\n // Max-heap of task counts\n PriorityQueue maxHeap = new PriorityQueue<>(Comparator.reverseOrder());\n for (int count : counts) {\n if (count > 0) maxHeap.offer(count);\n }\n\n int time = 0;\n while (!maxHeap.isEmpty()) {\n List temp = new ArrayList<>();\n\n // Process up to (cooldown + 1) tasks\n for (int i = 0; i <= cooldown; i++) {\n if (!maxHeap.isEmpty()) {\n int count = maxHeap.poll() - 1;\n if (count > 0) temp.add(count);\n }\n time++;\n\n if (maxHeap.isEmpty() && temp.isEmpty()) break;\n }\n\n // Add remaining tasks back\n maxHeap.addAll(temp);\n }\n\n return time;\n}\n```\n\n### Pattern 5: K Closest Points\n\n```java\npublic int[][] kClosest(int[][] points, int k) {\n // Max-heap by distance (keep k smallest)\n PriorityQueue maxHeap = new PriorityQueue<>(\n (a, b) -> distanceSquared(b) - distanceSquared(a)\n );\n\n for (int[] point : points) {\n maxHeap.offer(point);\n if (maxHeap.size() > k) {\n maxHeap.poll();\n }\n }\n\n return maxHeap.toArray(new int[k][2]);\n}\n\nprivate int distanceSquared(int[] point) {\n return point[0] * point[0] + point[1] * point[1];\n}\n```\n\n---\n\n## Deep Dive: PriorityQueue vs Alternatives\n\n### PriorityQueue vs TreeSet\n\n```java\n// PriorityQueue: Only guarantees min/max access\nPriorityQueue pq = new PriorityQueue<>();\npq.offer(5); pq.offer(3); pq.offer(7);\npq.peek(); // 3 - O(1)\npq.contains(5); // O(n) - linear search!\n// No random access, no range queries\n\n// TreeSet: Full sorted set with navigation\nTreeSet ts = new TreeSet<>();\nts.add(5); ts.add(3); ts.add(7);\nts.first(); // 3 - O(log n)\nts.contains(5); // O(log n)\nts.floor(4); // 3 - navigation query\n\n// When to use which:\n// PriorityQueue: Only need min/max, frequent add/remove\n// TreeSet: Need contains, range queries, or navigation\n```\n\n### PriorityQueue vs Sorted List\n\n```java\n// Sorted List: Good for rare updates, frequent random access\nList sorted = new ArrayList<>();\nsorted.add(5);\nCollections.sort(sorted); // O(n log n) per insert!\nsorted.get(0); // O(1) min access\n\n// PriorityQueue: Good for frequent updates, only min/max access\nPriorityQueue pq = new PriorityQueue<>();\npq.offer(5); // O(log n) per insert\npq.peek(); // O(1) min access\n\n// Break-even point:\n// If you insert n elements and only access min once: List might win\n// If you repeatedly access min: PriorityQueue always wins\n```\n\n### Performance Comparison\n\n| Operation | PriorityQueue | TreeSet | Sorted ArrayList |\n|-----------|--------------|---------|------------------|\n| offer/add | O(log n) | O(log n) | O(n) |\n| poll/removeFirst | O(log n) | O(log n) | O(n) or O(1)* |\n| peek/first | O(1) | O(log n) | O(1) |\n| contains | O(n) | O(log n) | O(log n)** |\n| remove(object) | O(n) | O(log n) | O(n) |\n\n*O(1) if removing from end, O(n) from beginning\n**With binary search\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Expecting Sorted Iteration\n\n```java\nPriorityQueue pq = new PriorityQueue<>(Arrays.asList(5, 2, 8, 1, 9));\n\n// ❌ WRONG: Iterator is NOT sorted!\nfor (Integer i : pq) {\n System.out.println(i); // Random heap order, NOT 1,2,5,8,9\n}\n\n// ✅ CORRECT: Poll for sorted order\nwhile (!pq.isEmpty()) {\n System.out.println(pq.poll()); // 1, 2, 5, 8, 9\n}\n```\n\n### Mistake 2: Modifying Elements After Adding\n\n```java\nclass Task {\n int priority;\n // getters, setters...\n}\n\nPriorityQueue pq = new PriorityQueue<>(\n Comparator.comparingInt(Task::getPriority)\n);\n\nTask task = new Task(5);\npq.offer(task);\n\n// ❌ WRONG: Modifying priority after adding\ntask.setPriority(1); // Heap doesn't know about this!\n// Heap structure is now invalid\n\n// ✅ CORRECT: Remove, modify, re-add\npq.remove(task);\ntask.setPriority(1);\npq.offer(task);\n```\n\n### Mistake 3: Using contains() Frequently\n\n```java\nPriorityQueue pq = new PriorityQueue<>();\n\n// ❌ WRONG: O(n) contains in loop\nfor (int i = 0; i < n; i++) {\n if (!pq.contains(nums[i])) { // O(n) each time!\n pq.offer(nums[i]);\n }\n}\n// Total: O(n²)\n\n// ✅ CORRECT: Use separate HashSet for membership\nSet seen = new HashSet<>();\nfor (int i = 0; i < n; i++) {\n if (seen.add(nums[i])) { // O(1)\n pq.offer(nums[i]);\n }\n}\n// Total: O(n log n)\n```\n\n### Mistake 4: Wrong Comparator Direction\n\n```java\n// ❌ WRONG: Natural order is min-heap, you wanted max\nPriorityQueue pq = new PriorityQueue<>();\npq.addAll(Arrays.asList(1, 5, 3));\npq.poll(); // Returns 1, not 5!\n\n// ✅ CORRECT: Reverse for max-heap\nPriorityQueue maxPq = new PriorityQueue<>(Comparator.reverseOrder());\nmaxPq.addAll(Arrays.asList(1, 5, 3));\nmaxPq.poll(); // Returns 5\n```\n\n### Mistake 5: Null Elements\n\n```java\nPriorityQueue pq = new PriorityQueue<>();\n\n// ❌ WRONG: PriorityQueue doesn't allow nulls\npq.offer(null); // 💥 NullPointerException\n\n// ✅ CORRECT: Handle nulls before adding\nString value = getValue();\nif (value != null) {\n pq.offer(value);\n}\n```\n\n---\n\n## 🐛 Debug This\n\n### Challenge 1: The Wrong Order\n\n```java\nPriorityQueue pq = new PriorityQueue<>(\n (a, b) -> a[0] - b[0]\n);\npq.offer(new int[]{3, 100});\npq.offer(new int[]{1, 200});\npq.offer(new int[]{2, 300});\n\nint sum = 0;\nwhile (!pq.isEmpty()) {\n sum += pq.poll()[1];\n}\nSystem.out.println(sum);\n```\n\n**✅ Answer:**\n\nOutput: `600`\n\nThe heap orders by first element (a[0]), so:\n- poll() returns {1, 200}, sum = 200\n- poll() returns {2, 300}, sum = 500\n- poll() returns {3, 100}, sum = 600\n\nAll elements are summed regardless of order.\n\n### Challenge 2: The Missing Update\n\n```java\nPriorityQueue pq = new PriorityQueue<>();\npq.offer(5);\npq.offer(3);\npq.offer(7);\n\nList list = new ArrayList<>(pq);\nCollections.sort(list);\n\nSystem.out.println(list);\nSystem.out.println(pq.poll());\n```\n\n**✅ Answer:**\n\nOutput:\n```text\n[3, 5, 7]\n3\n```\n\nCreating ArrayList from PriorityQueue copies elements in heap order (not sorted), then sort() sorts the list. PriorityQueue still works correctly, poll() returns minimum 3.\n\n### Challenge 3: The Comparator Confusion\n\n```java\nPriorityQueue pq = new PriorityQueue<>(\n Comparator.comparingInt(String::length)\n);\npq.offer(\"bb\");\npq.offer(\"aaa\");\npq.offer(\"c\");\n\nStringBuilder sb = new StringBuilder();\nwhile (!pq.isEmpty()) {\n sb.append(pq.poll());\n}\nSystem.out.println(sb);\n```\n\n**✅ Answer:**\n\nOutput: `cbbaaa`\n\nOrders by string length (ascending): \"c\" (1), \"bb\" (2), \"aaa\" (3)\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Kth Largest Element\n\nFind the kth largest element in an array:\n\n```java\npublic int findKthLargest(int[] nums, int k);\n// [3,2,1,5,6,4], k=2 → 5\n```\n\n**✅ Solution:**\n\n```java\npublic int findKthLargest(int[] nums, int k) {\n PriorityQueue minHeap = new PriorityQueue<>();\n\n for (int num : nums) {\n minHeap.offer(num);\n if (minHeap.size() > k) {\n minHeap.poll();\n }\n }\n\n return minHeap.peek();\n}\n// Time: O(n log k), Space: O(k)\n```\n\n### Exercise 2: Top K Frequent Elements\n\nFind k most frequent elements:\n\n```java\npublic int[] topKFrequent(int[] nums, int k);\n// [1,1,1,2,2,3], k=2 → [1,2]\n```\n\n**✅ Solution:**\n\n```java\npublic int[] topKFrequent(int[] nums, int k) {\n Map freq = new HashMap<>();\n for (int num : nums) {\n freq.merge(num, 1, Integer::sum);\n }\n\n PriorityQueue minHeap = new PriorityQueue<>(\n Comparator.comparingInt(freq::get)\n );\n\n for (int num : freq.keySet()) {\n minHeap.offer(num);\n if (minHeap.size() > k) {\n minHeap.poll();\n }\n }\n\n int[] result = new int[k];\n for (int i = k - 1; i >= 0; i--) {\n result[i] = minHeap.poll();\n }\n return result;\n}\n```\n\n### Exercise 3: Reorganize String\n\nRearrange string so no two adjacent chars are same:\n\n```java\npublic String reorganizeString(String s);\n// \"aab\" → \"aba\"\n// \"aaab\" → \"\" (impossible)\n```\n\n**✅ Solution:**\n\n```java\npublic String reorganizeString(String s) {\n int[] counts = new int[26];\n for (char c : s.toCharArray()) {\n counts[c - 'a']++;\n if (counts[c - 'a'] > (s.length() + 1) / 2) {\n return \"\"; // Impossible\n }\n }\n\n PriorityQueue maxHeap = new PriorityQueue<>(\n (a, b) -> b[1] - a[1]\n );\n\n for (int i = 0; i < 26; i++) {\n if (counts[i] > 0) {\n maxHeap.offer(new int[]{i, counts[i]});\n }\n }\n\n StringBuilder sb = new StringBuilder();\n while (maxHeap.size() >= 2) {\n int[] first = maxHeap.poll();\n int[] second = maxHeap.poll();\n\n sb.append((char) (first[0] + 'a'));\n sb.append((char) (second[0] + 'a'));\n\n if (--first[1] > 0) maxHeap.offer(first);\n if (--second[1] > 0) maxHeap.offer(second);\n }\n\n if (!maxHeap.isEmpty()) {\n sb.append((char) (maxHeap.poll()[0] + 'a'));\n }\n\n return sb.toString();\n}\n```\n\n### Exercise 4: Meeting Rooms II\n\nFind minimum meeting rooms required:\n\n```java\npublic int minMeetingRooms(int[][] intervals);\n// [[0,30],[5,10],[15,20]] → 2\n```\n\n**✅ Solution:**\n\n```java\npublic int minMeetingRooms(int[][] intervals) {\n if (intervals.length == 0) return 0;\n\n Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));\n\n // Min-heap of end times (rooms in use)\n PriorityQueue rooms = new PriorityQueue<>();\n rooms.offer(intervals[0][1]);\n\n for (int i = 1; i < intervals.length; i++) {\n // If earliest ending room is free\n if (intervals[i][0] >= rooms.peek()) {\n rooms.poll(); // Reuse room\n }\n rooms.offer(intervals[i][1]);\n }\n\n return rooms.size();\n}\n```\n\n### Exercise 5: Ugly Number II\n\nFind nth ugly number (factors only 2, 3, 5):\n\n```java\npublic int nthUglyNumber(int n);\n// n=10 → 12 (1,2,3,4,5,6,8,9,10,12)\n```\n\n**✅ Solution:**\n\n```java\npublic int nthUglyNumber(int n) {\n PriorityQueue minHeap = new PriorityQueue<>();\n Set seen = new HashSet<>();\n\n minHeap.offer(1L);\n seen.add(1L);\n\n int[] factors = {2, 3, 5};\n long current = 1;\n\n for (int i = 0; i < n; i++) {\n current = minHeap.poll();\n\n for (int factor : factors) {\n long next = current * factor;\n if (seen.add(next)) {\n minHeap.offer(next);\n }\n }\n }\n\n return (int) current;\n}\n```\n\n---\n\n## 🎤 Senior-Level Interview Questions\n\n### Question 1: Heap vs Balanced BST\n\n**Q: When would you use a heap vs a balanced BST (TreeSet)?**\n\n**A:**\n\n| Use Heap When | Use BST When |\n|---------------|--------------|\n| Only need min/max | Need any element access |\n| No contains() queries | Frequent contains() queries |\n| No range queries | Need range queries |\n| Memory constrained | Need navigation (floor, ceiling) |\n| Simple priority queue | Need ordered iteration |\n\n```java\n// Heap: Task scheduling - only need highest priority\nPriorityQueue tasks = new PriorityQueue<>(byPriority);\nTask next = tasks.poll();\n\n// BST: Price monitoring - need range and contains\nTreeSet prices = new TreeSet<>();\nprices.subSet(100, 200); // All prices in range\nprices.contains(150); // O(log n)\n```\n\n### Question 2: Heap Operations Complexity\n\n**Q: Explain the time complexity of building a heap from n elements.**\n\n**A:**\n\nTwo approaches:\n\n1. **Naive: offer() n times → O(n log n)**\n```java\nfor (int x : array) {\n heap.offer(x); // O(log n) each\n}\n```\n\n2. **Heapify: O(n)** - build from bottom up\n```java\n// Start from last non-leaf, sift down each\nfor (int i = n/2 - 1; i >= 0; i--) {\n siftDown(i);\n}\n```\n\nWhy O(n)? Half the nodes are leaves (no sift). Quarter sift 1 level. Eighth sift 2 levels. Sum: O(n).\n\nPriorityQueue(Collection) uses heapify: O(n).\n\n### Question 3: Streaming Top-K\n\n**Q: How do you maintain top-K elements from a stream efficiently?**\n\n**A:**\n\nUse a min-heap of size K:\n\n```java\nPriorityQueue topK = new PriorityQueue<>();\n\nvoid add(int num) {\n if (topK.size() < k) {\n topK.offer(num);\n } else if (num > topK.peek()) {\n topK.poll();\n topK.offer(num);\n }\n}\n```\n\n- Space: O(K)\n- Add: O(log K)\n- Get all K: O(K log K) if sorted needed\n\nFor top-K smallest, use max-heap instead.\n\n### Question 4: Two-Heap Pattern\n\n**Q: Explain the two-heap pattern for finding median.**\n\n**A:**\n\nSplit elements into two halves:\n- Max-heap: smaller half (root = largest of smaller)\n- Min-heap: larger half (root = smallest of larger)\n\n```java\n// Invariant: maxHeap.size() >= minHeap.size()\n// maxHeap.size() <= minHeap.size() + 1\n\nvoid add(int num) {\n maxHeap.offer(num); // Add to smaller half\n minHeap.offer(maxHeap.poll()); // Balance: move max to larger half\n if (minHeap.size() > maxHeap.size()) {\n maxHeap.offer(minHeap.poll()); // Keep sizes balanced\n }\n}\n\ndouble median() {\n if (maxHeap.size() > minHeap.size()) {\n return maxHeap.peek();\n }\n return (maxHeap.peek() + minHeap.peek()) / 2.0;\n}\n```\n\n### Question 5: Priority Queue vs Sorted List\n\n**Q: When is sorting better than using a priority queue?**\n\n**A:**\n\nSorting wins when:\n1. **One-time access**: Sort once, access all in order\n2. **Random access needed**: Sorted array/list has O(1) access\n3. **Infrequent updates**: Rebuilding is rare\n\nPriority Queue wins when:\n1. **Streaming data**: Elements arrive continuously\n2. **Only need min/max**: Don't need full ordering\n3. **Frequent updates**: Many add/remove operations\n\n```java\n// Sort: Process all events once\nList events = getEvents();\nevents.sort(byTime);\nfor (Event e : events) { ... } // O(n log n) total\n\n// PQ: Process events as they arrive\nPriorityQueue pq = new PriorityQueue<>(byTime);\nwhile (running) {\n pq.offer(newEvent); // O(log n)\n Event next = pq.poll(); // O(log n)\n}\n```\n\n### Question 6: Custom Object in PriorityQueue\n\n**Q: What happens if you don't provide a Comparator for a non-Comparable class?**\n\n**A:**\n\n```java\nclass Task {\n int priority;\n String name;\n}\n\nPriorityQueue pq = new PriorityQueue<>();\npq.offer(new Task()); // 💥 ClassCastException at runtime!\n\n// PriorityQueue tries to cast to Comparable:\n// ((Comparable) task1).compareTo(task2)\n\n// Fix 1: Implement Comparable\nclass Task implements Comparable {\n public int compareTo(Task other) {\n return Integer.compare(this.priority, other.priority);\n }\n}\n\n// Fix 2: Provide Comparator (preferred)\nPriorityQueue pq = new PriorityQueue<>(\n Comparator.comparingInt(t -> t.priority)\n);\n```\n\n---\n\n## 📝 Summary & Key Takeaways\n\n### Binary Heap Properties\n- Complete binary tree stored in array\n- Parent at (i-1)/2, children at 2i+1 and 2i+2\n- Min-heap: parent ≤ children (root is minimum)\n- Max-heap: parent ≥ children (root is maximum)\n\n### PriorityQueue Operations\n- offer()/poll(): O(log n)\n- peek(): O(1)\n- contains()/remove(Object): O(n) - avoid!\n- Building from collection: O(n)\n\n### Common Patterns\n- **Top-K**: Min-heap of size K for K largest\n- **Merge K Sorted**: Heap of K list heads\n- **Streaming Median**: Two heaps (max for smaller, min for larger)\n- **Task Scheduling**: Max-heap by priority\n\n### Best Practices\n- Use Comparator.reverseOrder() for max-heap\n- Don't modify elements after adding\n- Use HashSet alongside for O(1) contains\n- Poll for sorted iteration (iterator is NOT sorted)\n\n---\n\n## 🏁 Conclusion\n\nPriorityQueue 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.\n\nKey takeaways:\n1. **PriorityQueue is a min-heap by default** - use reversed comparator for max\n2. **Iterator is NOT sorted** - poll() for priority order\n3. **O(n) contains** - use HashSet alongside if needed\n4. **Don't modify elements** after adding (heap doesn't know)\n5. **Top-K pattern**: Use min-heap of size K for K largest elements\n\nIn the next article, we'll explore ConcurrentHashMap - the thread-safe map that powers concurrent Java applications without the performance penalties of synchronized collections.\n\n---\n\n## 📅 Review Schedule\n\nTo solidify your understanding, review this material:\n- **Tomorrow**: Implement Top-K pattern from memory\n- **In 3 days**: Practice streaming median problem\n- **In 1 week**: Explain heap vs BST tradeoffs\n- **In 2 weeks**: Review all common heap patterns\n\n---\n\n**Next in Series**: [Part 18: ConcurrentHashMap Fundamentals](/articles/java-collections-part-18-concurrenthashmap)\n\n**Series Navigation**: [Part 0: How to Use This Series](/articles/java-collections-part-0-how-to-use-this-series) | [Full Index](/articles/java-collections-compendium)\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:26.055848Z","createdAt","2026-06-10T07:19:26.056442Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",17,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Java","readingTime","seriesId",5,"seriesOrder","author",{"_31":55,"_99":57,"_100":101,"_102":103,"_104":-5,"_105":-5,"_106":-5,"_107":-5,"_108":-5},"category",{"_31":62,"_72":59,"_35":90,"_75":97,"_98":-5},"tags",[78,79,80,81,82],"series",{"_31":62,"_72":73,"_35":74,"_75":76,"_77":23},"name","Java Collections Compendium: From Fundamentals to Production Mastery","java-collections-compendium","description","A comprehensive 30-part series covering everything about Java Collections Framework. From foundational concepts like generics and equals/hashCode contract, through deep dives into ArrayList, LinkedList, HashMap, TreeMap, ConcurrentHashMap, to modern features like immutable collections, Java 21 sequenced collections, streams & collectors, and production patterns with JPA, Jackson & Spring. Includes real production stories, mental models, exercises, and 50+ interview questions.","isActive",{"_31":94,"_72":95,"_35":96},{"_31":91,"_72":92,"_35":93},{"_31":89,"_72":59,"_35":90},{"_31":86,"_72":87,"_35":88},{"_31":83,"_72":84,"_35":85},264,"Priorityqueue","priorityqueue",266,"Priority","priority",14,"java",265,"Heap","heap",354,"Binary Heap","binary-heap","Category for Java","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]