| Peek min/max (top of heap) | O(1) time |
| Insert (offer / bubble-up) | O(log n) time, O(1) extra space |
| Extract min/max (poll / sink-down) | O(log n) time |
| Build heap from n elements | O(n) time via bottom-up heapify, not O(n log n) |
| Search an arbitrary value | O(n) time — no ordering guarantee outside the root path |
| java.util.PriorityQueue internals | Resizable array-based binary min-heap, natural ordering by default |
| Kth largest element via heap | O(n log k) time, O(k) space |
| Heap sort | O(n log n) time, O(1) extra space, not stable |
Heaps & Priority Queues Interview Questions & Answers
Q1. What is a heap data structure?
A: A heap is a complete binary tree that satisfies the heap-order property: in a min-heap every parent's value is less than or equal to its children's values, and in a max-heap every parent's value is greater than or equal to its children's. This property guarantees the smallest (or largest) element is always at the root, giving O(1) peek access. Heaps are typically implemented over a plain array rather than linked nodes, since the tree is always complete (filled left to right, level by level).
Q2. What is the difference between a min-heap and a max-heap?
A: In a min-heap, the root always holds the smallest element and every parent is ≤ its children, making it ideal for repeatedly extracting the minimum. In a max-heap, the root holds the largest element and every parent is ≥ its children, ideal for repeatedly extracting the maximum. The two are structurally identical — only the comparison direction differs — so you can flip one into the other by negating keys or supplying a reversed comparator.
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // root = smallest
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // root = largestQ3. Why must a binary heap be a "complete" binary tree?
A: Completeness means every level is fully filled except possibly the last, which is filled left to right with no gaps. This guarantees the tree height is always ⌈log2(n+1)⌉, which is what keeps insert and extract at O(log n) — a heap can never degenerate into a skewed shape like an unbalanced BST can. Completeness is also exactly what allows the tree to be stored compactly in a plain array with no wasted slots and no null-child bookkeeping.
Q4. Why is a heap normally implemented with an array instead of node objects with left/right pointers?
A: Because the tree is always complete, the parent/child relationship can be computed arithmetically from the index instead of stored as pointers, so a plain array packs the tree with zero pointer overhead and excellent cache locality. Node-based heaps would need extra memory per node for left/right/parent references and would suffer more cache misses during heapify due to pointer chasing. Array-backed heaps are simpler, faster in practice, and are exactly what java.util.PriorityQueue uses internally.
Q5. What are the index formulas for finding a node's parent and children in an array-based heap?
A: For a node stored at index i (0-based array): its left child is at 2i + 1, its right child is at 2i + 2, and its parent is at (i - 1) / 2 using integer division. These formulas hold regardless of heap size and are the entire basis for navigating the tree without any pointers. If a computed child index is ≥ the heap's current size, that child simply doesn't exist yet.
Q6. What is "heapify up" (bubble-up / sift-up) and when is it used?
A: Heapify up restores the heap property after inserting a new element at the end of the array (the next free complete-tree slot). It repeatedly compares the new element to its parent and swaps upward while the heap property is violated, stopping when the parent is already smaller (min-heap) or the element reaches the root. Since the tree height is O(log n), this touches at most O(log n) nodes on a single root-to-leaf path.
void heapifyUp(int[] heap, int size) {
int i = size - 1;
while (i > 0) {
int parent = (i - 1) / 2;
if (heap[i] >= heap[parent]) break; // min-heap property satisfied
int t = heap[i]; heap[i] = heap[parent]; heap[parent] = t;
i = parent;
}
}Q7. What is "heapify down" (sift-down / sink) and when is it used?
A: Heapify down restores the heap property after removing the root: the last element is moved to the root position, then repeatedly compared against its smaller child (min-heap) and swapped down until it is smaller than both children or reaches a leaf. It also runs during the bottom-up array-to-heap construction (build-heap) at every internal node. Like heapify up, it touches at most one root-to-leaf path, so it costs O(log n).
void heapifyDown(int[] heap, int size, int i) {
while (true) {
int left = 2 * i + 1, right = 2 * i + 2, smallest = i;
if (left < size && heap[left] < heap[smallest]) smallest = left;
if (right < size && heap[right] < heap[smallest]) smallest = right;
if (smallest == i) break;
int t = heap[i]; heap[i] = heap[smallest]; heap[smallest] = t;
i = smallest;
}
}Q8. What is the time complexity of inserting an element into a heap?
A: Insertion is O(log n): the new element is appended at the next free array slot in O(1), then heapify-up moves it up at most tree-height-many levels, and the height of a complete binary tree with n nodes is O(log n). No other work is needed since the rest of the tree structure is untouched.
Q9. What is the time complexity of extracting the min/max element from a heap?
A: Extraction is O(log n): the root is removed and returned, the last array element is moved into the root position in O(1), and heapify-down restores order in O(log n) by descending a single root-to-leaf path. The shrink of the logical array size is also O(1).
Q10. What is the time complexity of peeking at the top of a heap without removing it?
A: Peek is O(1) because the minimum (or maximum) element is always stored at index 0 by the heap-order property — no traversal or comparison is required, just a direct array read.
Q11. How do you build a heap from an unordered array in O(n) time instead of O(n log n)?
A: Start heapify-down from the last non-leaf node (index n/2 - 1) and work backward to the root, calling heapify-down at each index. Although each call costs up to O(log n), most nodes are near the bottom of the tree where heapify-down does very little work, and a tight amortized analysis (summing work across all levels, weighted by how many nodes sit at each height) shows the total cost is O(n), not O(n log n).
void buildHeap(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapifyDown(arr, n, i);
}
}Q12. Why is the O(n) build-heap bound not obvious from "n calls to an O(log n) operation"?
A: Naively multiplying n nodes by O(log n) per heapify-down gives O(n log n), but that overcounts because heapify-down's actual cost depends on a node's height (distance to its farthest leaf), not the tree's overall height. Roughly half the nodes are leaves (height 0, free), a quarter have height 1, an eighth have height 2, and so on — summing height × node-count-at-that-height across a geometric series converges to O(n) total work, not O(n log n).
Q13. How does a heap differ from a binary search tree (BST)?
A: A heap only guarantees a weak parent-child ordering (parent ≤ children for a min-heap) and offers O(1) access to just the min/max, whereas a BST maintains a full ordering (left subtree < node < right subtree) that supports O(log n) search, in-order traversal for sorted output, and range queries — none of which a heap supports efficiently (searching an arbitrary value in a heap is O(n)). Heaps are also always complete and array-backed, while balanced BSTs (like a Red-Black tree or AVL tree) need explicit rebalancing logic and node pointers.
Q14. Why is a heap not fully sorted, and can you print heap elements in sorted order directly?
A: A heap only enforces order along each root-to-leaf path (parent vs. its own children); it says nothing about the relative order of two sibling subtrees or of nodes at the same depth. So you cannot simply read the backing array left to right and get sorted output — you must repeatedly extract the root (O(log n) each) to retrieve elements in sorted order, which is exactly what heap sort does.
Q15. When would you choose a heap over a fully sorted array or balanced BST for a given problem?
A: Choose a heap when you only ever need fast repeated access to the current minimum or maximum and don't care about full ordering, arbitrary search, or predecessor/successor queries — e.g., scheduling, top-K tracking, or graph shortest-path algorithms. A sorted array or balanced BST does more (full ordering, range queries, arbitrary lookup) but at a higher constant cost or worse insert complexity (O(n) for a sorted array insert vs. O(log n) for a heap).
Q16. What class does Java provide for a priority queue, and what is its default ordering?
A: java.util.PriorityQueue<E> is Java's built-in binary heap implementation. By default it is a min-heap using the elements' natural ordering (via Comparable), so poll() always returns the smallest element first. It is not synchronized and is part of the Collections Framework, implementing the Queue interface.
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(1); pq.offer(3);
System.out.println(pq.poll()); // 1 (smallest first)Q17. What internal data structure backs java.util.PriorityQueue?
A: It is backed by a resizable Object[] array representing a balanced binary heap, using the same index arithmetic (2i+1, 2i+2, (i-1)/2) as a hand-rolled array heap. It grows using a doubling-like strategy similar to ArrayList when capacity is exceeded, and it does not shrink automatically after removals.
Q18. How do you make java.util.PriorityQueue behave as a max-heap?
A: Since PriorityQueue is a min-heap by default, pass a comparator that reverses the natural order — either Collections.reverseOrder() for Comparable types, or a lambda like (a, b) -> b - a (careful with overflow; prefer Integer.compare(b, a)). The heap's internal mechanics don't change at all — only the comparison direction flips, which flips which element bubbles to the root.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
maxHeap.offer(5); maxHeap.offer(1); maxHeap.offer(9);
System.out.println(maxHeap.poll()); // 9 (largest first)Q19. How do you use a custom Comparator with PriorityQueue for objects, not primitives?
A: Pass a Comparator<T> to the constructor (or a lambda / method reference), and the heap will order elements according to whatever key that comparator extracts, without requiring the objects to implement Comparable. This is the standard pattern for problems like "top K frequent elements," where you order by a computed frequency rather than the object's own natural value.
record Task(String name, int priority) {}
PriorityQueue<Task> pq = new PriorityQueue<>(Comparator.comparingInt(Task::priority));
pq.offer(new Task("deploy", 2));
pq.offer(new Task("hotfix", 1));
System.out.println(pq.poll().name()); // "hotfix" (lowest priority number first)Q20. What is the difference between offer()/add() and poll()/remove() on PriorityQueue?
A: offer(e) and add(e) both insert an element and are functionally identical for PriorityQueue (both O(log n)) since it is effectively unbounded; add() is defined by the general Collection interface and throws if insertion fails, while offer() is the Queue-idiomatic version that returns false on failure (though PriorityQueue itself never rejects an offer). Likewise poll() removes and returns the head, returning null if empty, while remove() does the same but throws NoSuchElementException on an empty queue.
Q21. What is the difference between peek() and element() on PriorityQueue?
A: Both return the head of the queue (the min or max, per ordering) without removing it, but peek() returns null if the queue is empty while element() throws NoSuchElementException. This mirrors the poll()/remove() distinction: the "peek/poll" family is null-safe, the "element/remove" family is exception-based.
Q22. Is java.util.PriorityQueue thread-safe? What's the concurrent alternative?
A: No — PriorityQueue is not synchronized, and concurrent modification from multiple threads can corrupt the internal heap array or throw ConcurrentModificationException during iteration. For a thread-safe blocking priority queue, use java.util.concurrent.PriorityBlockingQueue, which supports the same ordering semantics but adds internal locking and blocking take()/put() operations suitable for producer-consumer pipelines.
Q23. Does iterating over a PriorityQueue with its Iterator return elements in sorted order?
A: No. The iterator returned by iterator() walks the backing array in whatever order the heap happens to store it, which only guarantees the root is smallest — it makes no guarantee about the relative order of any other pair of elements. To get elements in priority order you must repeatedly call poll() (destructively) or copy the queue and drain the copy.
Q24. Why must elements in a PriorityQueue be mutually comparable, and what happens if they aren't?
A: The heap needs a total ordering to decide where each element belongs relative to its parent and children, so elements must either implement Comparable consistently or the queue must be constructed with an explicit Comparator. If neither is provided, or if two elements throw when compared (e.g., mixing incompatible types), operations like offer() throw ClassCastException at runtime.
Q25. What is the time complexity of contains() and remove(Object) on PriorityQueue, and why?
A: Both are O(n) because the heap only orders elements along root-to-leaf paths — there's no way to binary-search for an arbitrary value, so the implementation must linearly scan the backing array. This is a common interview trap: removing an arbitrary (non-root) element from a heap is not O(log n) unless you maintain an auxiliary index-lookup structure (an indexed priority queue).
Q26. Can you insert a null element into a PriorityQueue?
A: No — PriorityQueue throws NullPointerException on inserting null. This is because the heap must be able to compare every element it holds, and null has no defined ordering relationship to other elements (comparing against null would throw anyway inside most Comparators/Comparable implementations).
Q27. How do you initialize a PriorityQueue with a pre-existing collection efficiently?
A: Pass the collection directly to the constructor, e.g., new PriorityQueue<>(list). Internally this uses the O(n) bottom-up build-heap algorithm rather than inserting elements one at a time (which would cost O(n log n) via n individual O(log n) offers), so it is meaningfully faster for large initial datasets.
List<Integer> nums = List.of(9, 4, 7, 1, 3);
PriorityQueue<Integer> pq = new PriorityQueue<>(nums); // O(n) build, not O(n log n)Q28. What happens when a PriorityQueue's backing array runs out of capacity?
A: Like ArrayList, it grows the internal array when full — allocating a new, larger array (roughly doubling for small queues, growing by 50% for larger ones) and copying existing elements over via Arrays.copyOf. This is an O(n) operation, but because it happens increasingly rarely as the queue grows, the amortized cost per insertion remains O(log n) (dominated by heapify-up, not the occasional resize).
Q29. Why is toArray() on a PriorityQueue not sorted, and how do you get a sorted array from it?
A: toArray() simply copies the internal heap array as-is, which only satisfies the heap property, not full sorted order. To get a sorted array, either repeatedly poll() into a result array/list until empty (destructive to the original queue), or copy the queue's elements into a new list and call Collections.sort() / Arrays.sort() separately.
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(9, 4, 7, 1, 3));
List<Integer> sorted = new ArrayList<>();
while (!pq.isEmpty()) sorted.add(pq.poll()); // drains in ascending orderQ30. Is java.util.PriorityQueue a stable data structure with respect to equal-priority elements?
A: No, PriorityQueue makes no ordering guarantee among elements with equal priority — the heap's internal swaps during heapify up/down can freely reorder ties. If you need FIFO tie-breaking among equal priorities, add a monotonically increasing sequence number as a secondary comparator key (or use a wrapper with an insertion-order tiebreaker).
Q31. How do you find the kth largest element in an unsorted array using a heap?
A: Maintain a min-heap of size k: push each element, and whenever the heap's size exceeds k, poll (remove) the smallest. After processing all n elements, the heap's root is exactly the kth largest, because the heap has continuously discarded everything smaller than the current top-k. This is O(n log k) time and O(k) space — better than full sort's O(n log n) when k is small.
int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int n : nums) {
minHeap.offer(n);
if (minHeap.size() > k) minHeap.poll();
}
return minHeap.peek();
}Q32. How do you find the kth smallest element in an unsorted array using a heap?
A: Mirror the kth-largest approach but with a max-heap of size k: push each element, and whenever size exceeds k, poll the largest. After the full scan, the root of the max-heap is the kth smallest, since the heap has been discarding everything larger than the current top-k smallest values. This is also O(n log k) time, O(k) space.
Q33. How do you find the top K frequent elements in an array?
A: First build a frequency map with a HashMap in O(n). Then use a min-heap of size k ordered by frequency: push each distinct (value, frequency) pair, popping the lowest-frequency entry whenever size exceeds k. The remaining k heap entries are the answer, giving O(n log k) overall — much better than sorting all distinct elements by frequency, which is O(n log n).
int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) freq.merge(n, 1, Integer::sum);
PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(freq::get));
for (int key : freq.keySet()) {
heap.offer(key);
if (heap.size() > k) heap.poll();
}
int[] result = new int[k];
for (int i = k - 1; i >= 0; i--) result[i] = heap.poll();
return result;
}Q34. How would you sort a "k-sorted" array (each element is at most k positions from its sorted position) efficiently?
A: Use a min-heap of size k+1: seed it with the first k+1 elements, then repeatedly poll the minimum (guaranteed correct since no smaller element can appear beyond k positions ahead) and push the next unread element. This produces sorted output in O(n log k) time and O(k) space, far better than a full O(n log n) sort when k is small relative to n.
Q35. How do you merge K sorted linked lists into one sorted list using a heap?
A: Seed a min-heap with the head node of each of the K lists, ordered by node value. Repeatedly poll the smallest node, append it to the result list, and if that node has a next node, push it into the heap. Each of the N total nodes across all lists is pushed and popped exactly once, so this runs in O(N log K) time and O(K) heap space — much better than merging lists pairwise, which is O(N×K).
ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
for (ListNode head : lists) if (head != null) heap.offer(head);
ListNode dummy = new ListNode(0), tail = dummy;
while (!heap.isEmpty()) {
ListNode node = heap.poll();
tail.next = node;
tail = node;
if (node.next != null) heap.offer(node.next);
}
return dummy.next;
}Q36. How do you merge K sorted arrays into one sorted array using a heap?
A: Seed a min-heap with the first element of each array, storing enough metadata (array index, element index) alongside the value to know where to fetch the next candidate. Repeatedly poll the minimum, append it to the result, and push the next element from the same source array if one remains. This is O(N log K) time, where N is the total number of elements across all K arrays — the same pattern used for merging K sorted linked lists.
Q37. How do you find the K closest points to the origin?
A: Use a max-heap of size k ordered by squared Euclidean distance (avoiding a sqrt call is a minor optimization since it doesn't change ordering). Push each point, and whenever the heap exceeds size k, pop the farthest point. After scanning all points, the heap holds exactly the k closest, in O(n log k) time and O(k) space — better than sorting everything by distance, which is O(n log n).
int[][] kClosest(int[][] points, int k) {
PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
(a, b) -> (b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1]));
for (int[] p : points) {
maxHeap.offer(p);
if (maxHeap.size() > k) maxHeap.poll();
}
return maxHeap.toArray(new int[0][]);
}Q38. How does the two-heap technique find the running median of a data stream?
A: Maintain a max-heap holding the smaller half of the numbers seen so far and a min-heap holding the larger half, keeping their sizes balanced (differing by at most 1). Every new number is inserted into one heap and then, if needed, rebalanced by moving the top element across to the other heap so that all values in the max-heap remain ≤ all values in the min-heap. The median is O(1) to read: either the max-heap's root (odd total count) or the average of both roots (even count); each insertion costs O(log n).
class MedianFinder {
PriorityQueue<Integer> lowerHalf = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
PriorityQueue<Integer> upperHalf = new PriorityQueue<>(); // min-heap
void addNum(int num) {
lowerHalf.offer(num);
upperHalf.offer(lowerHalf.poll());
if (upperHalf.size() > lowerHalf.size()) lowerHalf.offer(upperHalf.poll());
}
double findMedian() {
if (lowerHalf.size() > upperHalf.size()) return lowerHalf.peek();
return (lowerHalf.peek() + upperHalf.peek()) / 2.0;
}
}Q39. Why does the two-heap median technique rebalance by always routing through the max-heap first?
A: Always inserting into the max-heap (lower half) first and then immediately moving its new root into the min-heap (upper half) guarantees every value ends up compared against the boundary between the two halves before settling, which keeps the invariant "every lower-half value ≤ every upper-half value" correct regardless of where the new number actually belongs. The final size-balancing step (moving one element back if the min-heap grew too large) keeps the two halves within one element of each other, which is what makes the median O(1) to compute.
Q40. How do you maintain the median of a sliding window over a stream (sliding window median)?
A: Extend the two-heap technique with lazy deletion: keep the same balanced max-heap/min-heap split, but since a heap can't remove an arbitrary element in O(log n), track elements that are "logically removed" (fallen out of the window) in a HashMap of pending-deletion counts, and only actually pop them from a heap when they surface at the top during a rebalance or median read. This keeps each slide O(log n) amortized instead of degrading to O(n) per removal.
Q41. How do you solve the Task Scheduler problem (CPU tasks with a cooldown period) using a heap?
A: Count each task type's frequency, then push all frequencies into a max-heap. In each cycle, pop up to n+1 of the most frequent remaining tasks (where n is the cooldown), decrement their counts, and hold them in a temporary list; after the cycle, push back any tasks that still have remaining count. This greedily schedules the most frequent tasks first to spread them out, minimizing idle slots, and runs in O(total tasks × log 26) since at most 26 uppercase task types exist in the classic version.
int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
for (char t : tasks) freq[t - 'A']++;
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int f : freq) if (f > 0) maxHeap.offer(f);
int time = 0;
while (!maxHeap.isEmpty()) {
List<Integer> cycle = new ArrayList<>();
for (int i = 0; i <= n; i++) {
if (!maxHeap.isEmpty()) cycle.add(maxHeap.poll() - 1);
}
for (int c : cycle) if (c > 0) maxHeap.offer(c);
time += maxHeap.isEmpty() ? cycle.size() : n + 1;
}
return time;
}Q42. How do you rearrange a string so no two adjacent characters are the same (reorganize string)?
A: Count character frequencies and push them into a max-heap ordered by frequency. Repeatedly pop the two most frequent remaining characters, append one of each to the result, and push both back with decremented counts (skipping any that hit zero) — this greedily interleaves the most common characters so they never end up adjacent. If, at any point, only one character type remains and its count exceeds half the remaining length rounded up, no valid arrangement exists.
String reorganizeString(String s) {
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);
PriorityQueue<Character> heap = new PriorityQueue<>((a, b) -> freq.get(b) - freq.get(a));
heap.addAll(freq.keySet());
StringBuilder sb = new StringBuilder();
while (heap.size() > 1) {
char first = heap.poll(), second = heap.poll();
sb.append(first).append(second);
freq.put(first, freq.get(first) - 1);
freq.put(second, freq.get(second) - 1);
if (freq.get(first) > 0) heap.offer(first);
if (freq.get(second) > 0) heap.offer(second);
}
if (!heap.isEmpty()) {
char last = heap.poll();
if (freq.get(last) > 1) return "";
sb.append(last);
}
return sb.toString();
}Q43. How do you generate the nth ugly number (a number whose only prime factors are 2, 3, and 5) using a heap?
A: Use a min-heap seeded with 1, and a HashSet to avoid re-adding duplicates. Repeatedly pop the smallest value, and for each of the multipliers 2, 3, and 5, push the popped value times that multiplier if not already seen. After popping n times, the nth pop is the answer, since the heap always surfaces the next-smallest ugly number in order. This is O(n log n) time due to n heap operations, versus checking every integer's prime factorization which would be far slower.
Q44. How do you find the minimum cost to connect N ropes of different lengths (or merge stones) using a heap?
A: Push all rope lengths into a min-heap. Repeatedly pop the two shortest ropes, add their sum to the total cost, and push the merged rope back into the heap; repeat until only one rope remains. Greedily merging the two smallest pieces first (the same idea behind Huffman coding) minimizes total cost, and runs in O(n log n) since each of the n-1 merges does O(log n) heap work.
int connectRopes(int[] ropes) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int r : ropes) minHeap.offer(r);
int totalCost = 0;
while (minHeap.size() > 1) {
int first = minHeap.poll(), second = minHeap.poll();
int merged = first + second;
totalCost += merged;
minHeap.offer(merged);
}
return totalCost;
}Q45. How do you find K pairs with the smallest sums from two sorted arrays?
A: Use a min-heap seeded with pairs formed from the first array's elements combined with the second array's first element, ordered by sum. Repeatedly pop the smallest-sum pair, add it to the result, and push the next candidate pair (advancing the second array's index for that first-array element) if the result still needs more pairs. This avoids generating all m×n pairs up front, running in roughly O(k log k) instead of O(m×n log(m×n)).
Q46. How do you solve the "meeting rooms II" problem (minimum number of conference rooms needed) with a heap?
A: Sort meetings by start time, then use a min-heap of currently-occupied rooms' end times. For each meeting, if the earliest-ending room (heap root) frees up before or when this meeting starts, pop it and reuse that room (updating its end time); otherwise allocate a new room by pushing this meeting's end time onto the heap. The heap's maximum size reached during the scan is the answer, and this runs in O(n log n) dominated by the sort.
int minMeetingRooms(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> endTimes = new PriorityQueue<>();
for (int[] meeting : intervals) {
if (!endTimes.isEmpty() && endTimes.peek() <= meeting[0]) {
endTimes.poll();
}
endTimes.offer(meeting[1]);
}
return endTimes.size();
}Q47. How do you solve the IPO problem (maximize final capital by picking up to K projects) with two heaps?
A: Push all projects into a min-heap ordered by required capital. At each of the K rounds, move every project whose capital requirement is ≤ current available capital from the capital-heap into a max-heap ordered by profit, then pop the most profitable available project and add its profit to capital. This greedily always executes the best currently affordable project, running in O(n log n) total across all heap moves.
int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
int n = profits.length;
PriorityQueue<int[]> byCapital = new PriorityQueue<>((a, b) -> a[0] - b[0]);
PriorityQueue<int[]> byProfit = new PriorityQueue<>((a, b) -> b[1] - a[1]);
for (int i = 0; i < n; i++) byCapital.offer(new int[]{capital[i], profits[i]});
for (int i = 0; i < k; i++) {
while (!byCapital.isEmpty() && byCapital.peek()[0] <= w) {
byProfit.offer(byCapital.poll());
}
if (byProfit.isEmpty()) break;
w += byProfit.poll()[1];
}
return w;
}Q48. How do you find the kth smallest element in a row-wise and column-wise sorted matrix using a heap?
A: Seed a min-heap with the first element of each row (or just the top row's cells with their coordinates). Repeatedly pop the smallest element, and push the next element to its right in the same row (or below in the same column, depending on which axis you seed by) if it exists. After k pops, the last popped value is the kth smallest. This runs in O(k log n) time, much better than flattening and sorting the whole matrix at O(n² log n²) for large matrices.
int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int r = 0; r < Math.min(n, k); r++) heap.offer(new int[]{matrix[r][0], r, 0});
int result = -1;
for (int i = 0; i < k; i++) {
int[] top = heap.poll();
result = top[0];
int row = top[1], col = top[2];
if (col + 1 < n) heap.offer(new int[]{matrix[row][col + 1], row, col + 1});
}
return result;
}Q49. How do you find the smallest range that includes at least one number from each of K sorted lists?
A: Seed a min-heap with the first element of each of the K lists, also tracking the current maximum among the seeded elements. At each step, the range from the heap's minimum to the tracked maximum is a candidate; pop the minimum, advance that list's pointer, push its next element, update the running maximum, and repeat until any list is exhausted. Because the heap always evicts the current smallest element that's dragging the range down, this greedily narrows toward the true smallest valid range in O(N log K) time, where N is the total element count.
Q50. How do you solve the "employee free time" problem (find gaps common to everyone's schedule) using a heap?
A: Push the first interval of each employee's sorted schedule into a min-heap ordered by start time, tracking which employee/index each entry came from. Repeatedly pop the earliest interval, compare its start to the running "latest end seen so far" — a gap exists if there's a positive difference — then update the running end and push that employee's next interval if one remains. This merges all schedules in sorted order without fully concatenating and sorting every interval up front, running in O(N log K) for N total intervals across K employees.
Q51. How would you design a simplified Twitter feed that returns the 10 most recent tweets from followed users, using a heap?
A: Store each user's tweets as a list with monotonically increasing timestamps. To build a feed, seed a max-heap (ordered by timestamp) with the most recent tweet from each followed user (including self), then repeatedly pop the newest tweet, add it to the result, and push that same user's next-most-recent tweet — stopping once 10 tweets are collected. This is the same "merge K sorted sequences" pattern as merging K sorted lists, just ordered by recency instead of value, running in O(10 log K) rather than sorting every followed user's entire tweet history.
Q52. How do you find the single-threaded CPU's task execution order when tasks have arrival times and processing times, using a heap?
A: Sort tasks by arrival time. Maintain a min-heap of currently-available tasks ordered by (processing time, original index). Advance a simulated clock: push all tasks that have arrived by the current time into the heap, pop the shortest available task and execute it (advancing the clock by its processing time), and if no task is available yet, jump the clock forward to the next task's arrival time. This greedy "shortest available job next" strategy minimizes each task's completion lag and runs in O(n log n).
Q53. How does Dijkstra's algorithm use a min-heap to find shortest paths?
A: Dijkstra maintains a min-heap of (distance, vertex) pairs, always processing the vertex with the currently smallest known tentative distance next. When a vertex is popped, if it hasn't been finalized yet, it relaxes all its outgoing edges — for each neighbor, if going through the current vertex offers a shorter path, the neighbor's distance is updated and a new (updated distance, neighbor) entry is pushed onto the heap. The heap guarantees vertices are finalized in strictly increasing distance order, which is the core correctness argument for Dijkstra on graphs with non-negative edge weights.
int[] dijkstra(List<List<int[]>> adj, int src, int n) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
heap.offer(new int[]{0, src});
while (!heap.isEmpty()) {
int[] top = heap.poll();
int d = top[0], u = top[1];
if (d > dist[u]) continue; // stale entry, skip
for (int[] edge : adj.get(u)) {
int v = edge[0], weight = edge[1];
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
heap.offer(new int[]{dist[v], v});
}
}
}
return dist;
}Q54. Why is heap-based Dijkstra O((V + E) log V) rather than O(V²)?
A: Each edge relaxation that improves a distance pushes one new heap entry, so across the whole run there are O(E) pushes and pops, each costing O(log V) (since the heap holds at most O(E) or O(V) entries depending on implementation, both giving O(log V) with a Fibonacci/binary heap of vertex count V). Combined with O(V) initial vertex handling, the total is O((V + E) log V) — this beats the O(V²) array-scan version of Dijkstra on sparse graphs (E much smaller than V²), though the array version can actually win on very dense graphs where E approaches V².
Q55. Why does a "lazy deletion" approach work for handling stale heap entries in heap-based Dijkstra?
A: Since Java's PriorityQueue doesn't support an efficient decrease-key operation, Dijkstra implementations simply push a new (smaller-distance, vertex) entry every time a shorter path is found, leaving old, now-outdated entries in the heap rather than removing them. When an entry is popped, it's checked against the current best-known distance for that vertex — if the popped distance is greater than the recorded best, it's a stale entry and is simply skipped rather than processed. This trades a small amount of extra heap memory and pop-and-discard work for avoiding a much more complex indexed decrease-key implementation, and the asymptotic complexity remains O((V+E) log V).
Q56. How does Prim's algorithm for minimum spanning tree use a min-heap?
A: Prim's grows a minimum spanning tree one vertex at a time: starting from an arbitrary vertex, it maintains a min-heap of (edge weight, vertex) candidates connecting the tree to a not-yet-included vertex. It repeatedly pops the cheapest connecting edge, adds that vertex to the tree if not already included, and pushes all of the newly added vertex's edges to still-outside vertices. This is structurally almost identical to Dijkstra's heap loop, except it compares edge weight to the tree rather than cumulative path distance from the source.
int primMST(List<List<int[]>> adj, int n) {
boolean[] inMST = new boolean[n];
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
heap.offer(new int[]{0, 0}); // {weight, vertex}
int totalWeight = 0, edgesUsed = 0;
while (!heap.isEmpty() && edgesUsed < n) {
int[] top = heap.poll();
int weight = top[0], u = top[1];
if (inMST[u]) continue;
inMST[u] = true;
totalWeight += weight;
edgesUsed++;
for (int[] edge : adj.get(u)) {
if (!inMST[edge[0]]) heap.offer(new int[]{edge[1], edge[0]});
}
}
return totalWeight;
}Q57. What is the key conceptual difference between how Dijkstra and Prim's algorithm use their heaps?
A: Dijkstra's heap orders vertices by cumulative shortest-path distance from a fixed source, so a popped vertex's distance is final and globally shortest. Prim's heap orders candidate edges by their individual weight connecting the growing tree to the rest of the graph, with no notion of cumulative distance at all — it only cares about the cheapest single edge crossing the tree's boundary at each step, which is why Prim's works correctly even with negative edge weights while Dijkstra's does not.
Q58. What is the "decrease-key" operation, and why doesn't java.util.PriorityQueue support it directly?
A: Decrease-key updates an existing heap element's priority to a smaller value and restores heap order in O(log n), which is essential for the "classic" textbook versions of Dijkstra and Prim that keep exactly one entry per vertex. A plain array-backed binary heap has no O(1) way to locate an arbitrary element's index, so decreasing its key would require an O(n) search first; java.util.PriorityQueue deliberately omits this operation, which is why Java implementations instead use the lazy-deletion/stale-entry trick of pushing duplicate, updated entries.
Q59. How does the A* search algorithm use a priority queue differently from plain Dijkstra?
A: A* uses a min-heap ordered by f(n) = g(n) + h(n), where g(n) is the actual cost from the start to node n (same as Dijkstra's distance) and h(n) is a heuristic estimate of the remaining cost to the goal. This heuristic biases the search to expand nodes that look promising toward the goal first, letting A* often explore far fewer nodes than Dijkstra while still guaranteeing the shortest path, provided h(n) is admissible (never overestimates the true remaining cost).
Q60. How does Huffman coding use a min-heap to build an optimal prefix code?
A: Compute each character's frequency and push every character as a leaf node into a min-heap ordered by frequency. Repeatedly pop the two lowest-frequency nodes, create a new internal node whose frequency is their sum and whose children are the two popped nodes, and push it back — continuing until only one node (the tree root) remains. Because it always merges the two currently cheapest subtrees first, this greedy process (identical in structure to the "connect ropes" problem) provably minimizes total weighted code length, running in O(n log n).
Q61. How would you solve "network delay time" (time for a signal to reach all nodes) using a heap?
A: This is Dijkstra's algorithm applied directly: run heap-based Dijkstra from the source node to compute the shortest time to every other node, then the answer is the maximum value among all reachable nodes' shortest distances (or -1 if any node is unreachable). It runs in O((V + E) log V) using the same min-heap relaxation loop.
int networkDelayTime(int[][] times, int n, int k) {
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int[] t : times) adj.get(t[0]).add(new int[]{t[1], t[2]});
int[] dist = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[k] = 0;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
heap.offer(new int[]{0, k});
while (!heap.isEmpty()) {
int[] top = heap.poll();
int d = top[0], u = top[1];
if (d > dist[u]) continue;
for (int[] e : adj.get(u)) {
if (dist[u] + e[1] < dist[e[0]]) {
dist[e[0]] = dist[u] + e[1];
heap.offer(new int[]{dist[e[0]], e[0]});
}
}
}
int maxDist = 0;
for (int i = 1; i <= n; i++) {
if (dist[i] == Integer.MAX_VALUE) return -1;
maxDist = Math.max(maxDist, dist[i]);
}
return maxDist;
}Q62. How do you adapt Dijkstra with a heap to solve "cheapest flights within K stops"?
A: Augment the heap entries with a stop count: push (cost, city, stopsUsed), and only relax an edge (push a new entry) if stopsUsed <= K, incrementing it for each hop. Unlike plain Dijkstra, you cannot simply skip a city because it was already visited with a lower cost, since a path with more stops but still ≤ K might be the only valid one — so the "stale skip" optimization must be relaxed for the constrained-stops variant, and the heap comparison is still purely by cost.
Q63. Why is a heap the standard choice for graph algorithms that need "always process the smallest/next-best candidate," rather than repeatedly scanning an array?
A: A plain array approach to Dijkstra scans all V vertices to find the minimum-distance unvisited one each iteration, costing O(V) per extraction and O(V²) total — fine for dense graphs but wasteful for sparse ones. A heap turns that extraction into O(log V), and since sparse real-world graphs (E close to V, not V²) are common in interview and production settings, the heap-based O((V+E) log V) approach is asymptotically better in the vast majority of practical cases.
Q64. How does the classic array-based (non-heap) Dijkstra compare against heap-based Dijkstra in complexity?
A: Array-based Dijkstra runs in O(V²) since it does a linear scan for the minimum-distance unvisited vertex on every one of V iterations, with O(1) edge relaxations. Heap-based Dijkstra runs in O((V+E) log V), which is asymptotically better whenever E is o(V² / log V) — true for most sparse graphs — but the array version can actually be competitive or faster on dense graphs (E close to V²) because it avoids heap bookkeeping overhead entirely.
Q65. What is heap sort, and what does it use a heap for?
A: Heap sort first builds a max-heap from the entire input array in O(n) using bottom-up heapify. It then repeatedly swaps the root (the current maximum) with the last unsorted element, shrinks the "heap region" by one, and calls heapify-down on the new root to restore heap order — repeating this n-1 times places every element into its final sorted position, in place. The array itself serves as both the heap's storage and the growing sorted output region simultaneously.
void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) heapifyDown(arr, n, i); // O(n) build max-heap
for (int end = n - 1; end > 0; end--) {
int t = arr[0]; arr[0] = arr[end]; arr[end] = t; // move max to sorted tail
heapifyDown(arr, end, 0); // restore heap on the shrunk region
}
}Q66. What is the time and space complexity of heap sort?
A: Heap sort is O(n log n) in the best, average, and worst case — unlike quicksort, its worst case doesn't degrade, because build-heap is O(n) and each of the n extraction/heapify-down steps is O(log n). It runs in O(1) extra space since the max-heap is built and consumed entirely within the input array, making it the standard in-place O(n log n) sort when guaranteed worst-case time matters more than average-case speed or stability.
Q67. Is heap sort a stable sorting algorithm?
A: No — heap sort is not stable. Building and maintaining the heap involves swaps that can freely reorder equal-priority elements relative to each other (e.g., during heapify-down, an element may hop past an equal one deeper in the tree), so two equal elements' original relative order is not guaranteed to be preserved in the sorted output.
Q68. How does heap sort compare to quicksort and merge sort in practice?
A: Heap sort guarantees O(n log n) worst case and O(1) extra space, but its poor cache locality (heapify jumps around the array via index arithmetic rather than accessing memory sequentially) usually makes it slower in practice than a well-implemented quicksort, whose average case is also O(n log n) with much better cache behavior — quicksort's downside is an O(n²) worst case on adversarial input. Merge sort guarantees O(n log n) worst case and is stable, but needs O(n) auxiliary space, unlike heap sort's O(1). Interviewers often ask you to justify heap sort specifically when worst-case time and in-place memory both matter, e.g., in embedded or memory-constrained systems.
Q69. During heap sort, why does the "sorted region" grow from the end of the array backward?
A: After building the max-heap, the algorithm swaps the current maximum (the root) into the last unsorted array slot, which places it in its correct final sorted position without needing extra storage. The heap's logical size then shrinks by one (excluding that now-sorted slot from further heap operations), so subsequent heapify-down calls never touch already-sorted elements — the sorted region silently grows backward from index n-1 toward index 0 while the "live heap" shrinks forward from index 0.
Q70. What is a d-ary heap, and how does it generalize a binary heap?
A: A d-ary heap is a heap where each node has up to d children instead of 2, using index formulas children of i = d*i + 1 .. d*i + d and parent of i = (i - 1) / d. It's a straightforward generalization of a binary heap (d=2) that trades tree height for branching factor: a d-ary heap of n elements has height O(log_d n), which is shallower than a binary heap's O(log_2 n) for d > 2.
Q71. What are the complexity trade-offs of using a d-ary heap instead of a binary heap?
A: Insert (heapify-up) becomes faster with larger d, since the tree is shallower — O(log_d n) instead of O(log_2 n). But extract-min/max (heapify-down) becomes slower, because at each level the operation must compare the current node against all d children to find the minimum instead of just 2, costing O(d × log_d n) overall rather than O(log_2 n). So d-ary heaps favor insert-heavy workloads at the cost of slower extraction, and the optimal d depends on the ratio of inserts to extractions in the workload.
Q72. When would you actually choose a d-ary heap over a binary heap in a real system or interview answer?
A: Choose a d-ary heap (commonly a 4-ary or higher heap) when insertions vastly outnumber extractions, or when better cache locality matters — a wider, shallower tree touches fewer distinct cache lines per insert. Dijkstra's algorithm on graphs with many more edges than vertices (insert-heavy relaxations relative to extractions) is a classic case where 4-ary heaps have been shown to measurably outperform binary heaps in practice, despite the same asymptotic complexity class.
Q73. What is an indexed priority queue (IPQ), and what problem does it solve?
A: An indexed priority queue augments a standard heap with a reverse lookup — typically an array mapping each element's identity (e.g., a vertex ID) to its current index in the heap array — so that decrease-key and arbitrary removal can be performed in O(log n) instead of the O(n) search a plain heap requires. It solves exactly the gap that forces Dijkstra/Prim implementations to fall back on lazy deletion: it lets you find and update "the entry for vertex v" directly without scanning.
Q74. How is an indexed priority queue typically implemented?
A: Maintain two parallel arrays alongside the heap array: position[id] gives the current heap-array index for a given element id, and heapKeyByPosition[i] (or the reverse mapping) gives which id sits at heap index i. Every swap performed during heapify-up/down must update both position-tracking arrays in lockstep with the value swap, so that position[id] always stays accurate — this bookkeeping is what turns "find and update element id's priority" from an O(n) scan into an O(1) lookup followed by an O(log n) heapify.
class IndexedMinHeap {
int[] heap; // heap[i] = id stored at heap position i
int[] position; // position[id] = current heap index of that id
int[] keys; // keys[id] = priority value for that id
int size;
void decreaseKey(int id, int newKey) {
keys[id] = newKey;
int i = position[id];
while (i > 0 && keys[heap[(i - 1) / 2]] > keys[heap[i]]) {
int parent = (i - 1) / 2;
swap(i, parent); // swap() also updates position[] for both ids
i = parent;
}
}
}Q75. What is the practical benefit of an indexed priority queue for Dijkstra and Prim's algorithm specifically?
A: With an IPQ, Dijkstra and Prim can maintain exactly one heap entry per vertex and call decrease-key when a shorter distance or cheaper connecting edge is found, instead of pushing duplicate stale entries and skipping them later. This keeps the heap's size bounded by V rather than E, which reduces memory usage on graphs with many edges and avoids the (small) wasted work of popping and discarding stale entries — the asymptotic time complexity stays O((V+E) log V) either way, so the benefit is mainly constant-factor and memory efficiency rather than a better complexity class.
Q76. How does a binary heap's decrease-key complexity compare to a Fibonacci heap's?
A: A binary heap's decrease-key (with index tracking, i.e., an IPQ) is O(log n) because it must heapify-up after lowering a key. A Fibonacci heap achieves amortized O(1) decrease-key by using lazy consolidation (marking and cutting subtrees rather than immediately restoring full order), which is why the theoretically optimal Dijkstra runtime is O(E + V log V) using a Fibonacci heap instead of O((E + V) log V) with a binary heap. In practice, Fibonacci heaps have high constant-factor overhead and complex implementation, so binary/d-ary heaps (or IPQs) remain far more common in real code and interviews.
Q77. What are leftist heaps and skew heaps, briefly?
A: Both are pointer-based (not array-based) mergeable heaps designed around an efficient O(log n) "merge two heaps into one" operation, which a standard binary heap cannot do efficiently (merging two array-backed binary heaps naively costs O(n)). A leftist heap maintains a "null path length" invariant to keep merges balanced; a skew heap achieves similar behavior more simply by unconditionally swapping children on every recursive merge step, trading a strict invariant for a simpler amortized-O(log n) implementation.
Q78. What is a binomial heap, briefly?
A: A binomial heap is a collection ("forest") of binomial trees, each satisfying the heap property, structured so the tree sizes correspond to the binary representation of the total element count — much like how binary representation underlies binary counters. It supports merging two heaps in O(log n) and decrease-key/delete in O(log n), making it a middle ground between a plain binary heap (fast per-op but slow merge) and a Fibonacci heap (fastest amortized decrease-key but more complex).
Q79. What is a pairing heap, briefly?
A: A pairing heap is a simpler, more practically efficient alternative to a Fibonacci heap: it's a multi-way tree where the minimum is always the root, insert and merge are O(1), and decrease-key is done by cutting a subtree and merging it back with the root. Its worst-case bounds are harder to prove tightly than a Fibonacci heap's, but empirically it tends to outperform Fibonacci heaps in real workloads due to lower constant-factor overhead and a much simpler implementation.
Q80. What is a min-max heap, and what problem does it solve?
A: A min-max heap is a single heap structure that supports O(1) access to both the minimum and the maximum simultaneously, and O(log n) insertion/removal of either. It alternates the ordering constraint by level — even levels enforce a min-heap-like relationship to their descendants, odd levels enforce a max-heap-like relationship — which lets it act as a double-ended priority queue without maintaining two separate heaps.
Q81. How would you implement a double-ended priority queue in Java without a dedicated min-max heap?
A: The common workaround is to maintain two synchronized heaps — one min-heap and one max-heap over the same logical dataset — plus a way to locate a given element in both (similar to an indexed priority queue) so it can be removed from both structures consistently when popped from either end. This costs more memory and bookkeeping than a true min-max heap but is far simpler to implement correctly, and is the pragmatic interview-friendly answer when a real min-max heap implementation isn't required.
Q82. When would you use a TreeMap/TreeSet instead of a heap for a "priority" style problem?
A: A TreeMap/TreeSet (backed by a Red-Black tree) supports everything a heap does — O(log n) insert, O(log n) removal of the min or max via firstKey()/lastKey() — plus O(log n) arbitrary search, O(log n) removal of any element by value, and ordered traversal/range queries, all of which a plain heap can't do efficiently. The cost is a higher constant factor per operation than an array-backed heap; choose TreeMap/TreeSet when you need those extra query capabilities (e.g., "find the next largest element ≥ x" or "remove this specific element"), and a plain heap when you only ever need repeated min/max extraction.
Q83. What is the "bounded priority queue" pattern for tracking the top K elements while streaming through n items?
A: Maintain a heap capped at size K, oriented so its root is the "worst" element currently in the top-K set (a min-heap root is the worst of the top-K-largest, and vice versa). For each streamed item, push it, and if the heap now exceeds size K, pop the root to evict the worst element. This keeps memory bounded at O(K) instead of O(n), and total time is O(n log K) — the pattern behind kth-largest, top-K-frequent, and K-closest-points solutions.
PriorityQueue<Integer> topKHeap = new PriorityQueue<>(); // min-heap, root = weakest of the top K
for (int value : stream) {
topKHeap.offer(value);
if (topKHeap.size() > K) topKHeap.poll(); // evict the weakest
}
// topKHeap now holds exactly the K largest values seen so farQ84. What is "lazy deletion" as a general heap design pattern, and where else does it show up beyond Dijkstra?
A: Lazy deletion defers actually removing a stale or invalidated entry from the heap until it happens to surface at the root, instead of searching for and removing it immediately (which a plain heap can't do in less than O(n) anyway). Beyond Dijkstra, it shows up in sliding-window-median implementations (elements that fell out of the window are marked for removal and skipped when popped) and in event-driven simulations where scheduled events can be cancelled — the pattern trades a small amount of extra memory and occasional wasted pops for avoiding an O(n) targeted deletion.
Q85. How do you build a max-heap in Java using PriorityQueue's natural min-heap behavior and a negation trick?
A: If elements are numeric, you can insert their negation into a standard min-heap and negate again on extraction — the smallest negated value corresponds to the largest original value. This avoids writing a custom comparator, though it's less readable than Collections.reverseOrder() and only works cleanly for numeric types without overflow risk (e.g., negating Integer.MIN_VALUE overflows), so a reversed comparator is generally the safer, preferred approach in production code.
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int n : new int[]{5, 1, 9, 3}) minHeap.offer(-n); // insert negated
int currentMax = -minHeap.poll(); // negate back on extraction -> 9Q86. How do you handle ties (equal priorities) with a well-defined tiebreaker in a Java PriorityQueue?
A: Chain a secondary comparator with thenComparing() (or thenComparingInt()) so that whenever the primary key is equal, a deterministic secondary key — such as an insertion sequence number, alphabetical name, or a stable ID — decides the order. Without an explicit tiebreaker, PriorityQueue's internal swaps can present equal-priority elements in an arbitrary, implementation-dependent order.
record Job(int priority, long seq) {}
PriorityQueue<Job> pq = new PriorityQueue<>(
Comparator.comparingInt(Job::priority).thenComparingLong(Job::seq)); // FIFO among equal prioritiesQ87. Does PriorityQueue.clone() perform a deep or shallow copy?
A: clone() performs a shallow copy: it creates a new PriorityQueue instance with a copy of the backing array (so the two queues' internal arrays are independent and can be modified separately), but the elements themselves are not cloned — both queues reference the exact same underlying objects. Mutating a shared mutable element through one queue's reference is visible through the other queue as well.
Q88. Why does calling toString() on a PriorityQueue not print elements in priority order, and is this a common bug source?
A: toString() (inherited from AbstractCollection) just walks the iterator, which — as with any iteration over PriorityQueue — reflects the raw backing-array order, not sorted priority order. Yes, this is a frequent source of confusion in debugging: developers sometimes assume printing or logging a PriorityQueue shows elements "in order," write logic that depends on that assumption, and get subtly wrong results; the safe habit is to always extract via poll() when order actually matters.
Q89. What exception does PriorityQueue throw when you poll(), remove(), peek(), or element() on an empty queue?
A: poll() and peek() return null on an empty queue rather than throwing. remove() and element(), by contrast, throw NoSuchElementException when the queue is empty, consistent with the general Queue interface's null-safe vs. exception-based method pairs.
Q90. What is the space complexity of a heap holding n elements, and does it depend on the tree's shape?
A: A heap uses O(n) space regardless of shape, because it is always a complete binary tree stored densely in an array with no wasted null slots — unlike an arbitrary (non-complete) binary tree, which can waste space on unbalanced structure or require extra pointer fields per node. This O(n), pointer-free storage is one of the main practical advantages of array-backed heaps over pointer-based tree structures.
Q91. What are real-world systems that rely on priority queues / heaps internally?
A: Operating system CPU schedulers use priority queues to pick the next process to run based on priority or estimated remaining time; event-driven simulations and discrete-event systems use a min-heap of "next event time" to process events in chronological order; network routers use Dijkstra-style shortest-path computations with heaps; and job-scheduling systems (task queues, load balancers) use priority queues to decide which job or request to service next based on urgency, deadline, or fairness weighting.
Q92. What is the difference between "heapify" as a verb applied to a single element versus "build-heap" applied to a whole array?
A: "Heapify" (heapify-up or heapify-down) restores the heap property for a single element that may have just been inserted, removed, or updated, touching only its root-to-leaf path in O(log n). "Build-heap" applies heapify-down at every internal node from the last non-leaf up to the root, transforming an entire unordered array into a valid heap in O(n) total — it's the batch operation built from repeated single-element heapify calls, but its aggregate cost is not simply n × O(log n) due to the height-weighted analysis covered earlier.
Q93. Why can't you binary-search a heap's backing array for an arbitrary value?
A: Binary search requires the array to be fully sorted so that comparing the midpoint tells you which half to discard; a heap's array is only partially ordered (parent ≤ children along each path), so the left half of the array is not guaranteed to be entirely less than the right half, or anything close to it. This is exactly why searching an arbitrary value in a heap is O(n), not O(log n) — you must fall back to a full linear scan (or maintain an auxiliary index structure, as in an IPQ, to avoid it).
Q94. How do you convert a max-heap into a min-heap (or vice versa) in place?
A: There's no O(1) trick — you must effectively rebuild: extract every element from the source heap in O(n log n) total time and either negate values and re-heapify, or simply call build-heap again with the opposite comparison to run heapify-down at every internal node in O(n). The O(n) build-heap-with-opposite-comparator approach is preferred over draining and reinserting element by element, which would cost O(n log n).
Q95. What is the worst-case time complexity of inserting n elements one at a time into an initially empty PriorityQueue?
A: O(n log n) overall, since each of the n individual offer() calls costs O(log n) in the worst case (heapify-up potentially climbing all the way to the root), even though the amortized cost of any occasional backing-array resize is folded into that bound. This is worse than passing all n elements to the constructor at once, which triggers the O(n) bulk build-heap path instead.
Q96. How would you detect whether an array actually represents a valid min-heap?
A: Iterate every index i from 0 up to the last non-leaf node, and for each, verify that arr[i] <= arr[2i+1] (if that child index is in bounds) and arr[i] <= arr[2i+2] (if in bounds); if any comparison fails, the array is not a valid heap. This check is O(n) since it inspects each parent-child relationship exactly once, and it correctly does not require the array to be fully sorted — only the local parent-child invariant needs to hold everywhere.
boolean isValidMinHeap(int[] arr) {
int n = arr.length;
for (int i = 0; i <= n / 2 - 1; i++) {
int left = 2 * i + 1, right = 2 * i + 2;
if (left < n && arr[i] > arr[left]) return false;
if (right < n && arr[i] > arr[right]) return false;
}
return true;
}Q97. Why is repeatedly calling Collections.sort() on an ArrayList a common anti-pattern where a heap should be used instead?
A: If a program needs to repeatedly find and remove the current minimum/maximum from a changing collection (e.g., a scheduler picking the next task after new ones keep arriving), re-sorting the whole list after every change costs O(n log n) per operation. A heap does the same job — always exposing the current min/max — in O(log n) per insert or extraction, which is asymptotically far better whenever this "insert then repeatedly extract the best" pattern happens more than a handful of times.
Q98. What is the time complexity of finding the median of an unsorted array using a heap-based approach versus full sorting?
A: A one-shot median of a static array is most simply found via full sort (O(n log n)) or, better, Quickselect for a single order statistic (average O(n)). The two-heap technique's real value is for a data stream where the median must be queried after every insertion — there, maintaining balanced heaps gives O(log n) per insertion with O(1) median reads, versus O(n log n) to re-sort from scratch after every single new element.
Q99. How would you find the running maximum of every window of size k in an array — and why is a heap not the optimal choice here?
A: A heap-based sliding window maximum works (push each element with its index, pop stale/out-of-window entries lazily from the top) but costs O(n log n) since a heap doesn't support O(1) removal of the element that just left the window unless it happens to be the current max. The optimal solution instead uses a monotonic deque that keeps indices in decreasing value order, achieving O(n) total — a good example of where a heap is a correct but not asymptotically optimal tool, and interviewers often probe whether you know the better alternative.
Q100. How do you find the maximum sum of K non-adjacent... actually, how do you efficiently maintain the top K elements seen so far, allowing duplicates, using a heap?
A: Use the standard bounded min-heap-of-size-K pattern: offer each new value, and if the heap size exceeds K, poll the smallest. Duplicates are handled naturally since a heap is a multiset by nature — it has no problem storing the same value more than once, unlike a TreeSet-based approach which would silently collapse duplicate keys unless wrapped with a counter or made into a TreeMap of value-to-count.
Q101. What is the amortized cost consideration when a PriorityQueue's backing array needs to grow during a long sequence of offer() calls?
A: Just like ArrayList, the occasional O(n) array-copy triggered by a resize is amortized across all the O(1)-capacity-available offers that came before it, so across n total insertions the resize overhead sums to O(n), keeping the amortized per-offer cost at O(log n) (dominated by heapify-up, not the resize). A single specific offer() call can still spike to O(n + log n) when it happens to trigger the resize.
Q102. Why might an interviewer ask you to implement a heap from scratch instead of just using java.util.PriorityQueue?
A: Using the built-in PriorityQueue tests whether you know the API; implementing one from scratch tests whether you actually understand the array-index arithmetic, heapify-up/down mechanics, and the O(n) vs O(n log n) build-heap distinction that the library hides behind a single method call. It's also the only way to demonstrate features PriorityQueue doesn't expose, like an efficient decrease-key (an indexed priority queue) or a custom d-ary branching factor.
Q103. How would you extend PriorityQueue's array-heapify logic to support a d-ary heap in Java (conceptually)?
A: Replace the fixed child-index formulas (2i+1, 2i+2) with the generalized d-ary formulas (d*i + 1 through d*i + d for children, (i-1)/d for parent), and change heapify-down to compare the current node against all d children (instead of just 2) to find the extreme value to swap with. Everything else — the array backing, the O(n) build-heap loop, the amortized-O(1) append — carries over unchanged; only the branching arithmetic and the per-node comparison fan-out differ.
void dAryHeapifyDown(int[] heap, int size, int i, int d) {
while (true) {
int smallest = i;
for (int c = 1; c <= d; c++) {
int child = d * i + c;
if (child < size && heap[child] < heap[smallest]) smallest = child;
}
if (smallest == i) break;
int t = heap[i]; heap[i] = heap[smallest]; heap[smallest] = t;
i = smallest;
}
}Q104. What is a common off-by-one mistake when implementing heapify manually, and how do you avoid it?
A: The most frequent bug is using the wrong bound when checking whether a computed child index exists — comparing against the array's allocated capacity instead of the heap's current logical size, which can let heapify-down read or swap with garbage/stale data beyond the "real" elements. Always compare child indices against a tracked size variable (the count of valid heap elements), not array.length, especially when the heap is implemented over a pre-allocated array with unused trailing capacity.
Q105. How do you efficiently find the top K frequent words, breaking ties alphabetically, using a heap?
A: Build a frequency map, then use a min-heap of size K ordered first by ascending frequency and, for ties, by descending alphabetical order (so that when the heap must evict its "weakest" entry, it correctly evicts the lowest-frequency, latest-alphabetically word first). After processing all words, drain the heap and reverse the result, since the heap naturally surfaces the weakest entries first, not the strongest. This runs in O(n log K) time.
List<String> topKFrequentWords(String[] words, int k) {
Map<String, Integer> freq = new HashMap<>();
for (String w : words) freq.merge(w, 1, Integer::sum);
PriorityQueue<String> heap = new PriorityQueue<>((a, b) ->
freq.get(a).equals(freq.get(b)) ? b.compareTo(a) : freq.get(a) - freq.get(b));
for (String w : freq.keySet()) {
heap.offer(w);
if (heap.size() > k) heap.poll();
}
LinkedList<String> result = new LinkedList<>();
while (!heap.isEmpty()) result.addFirst(heap.poll());
return result;
}Q106. How do you use a heap to solve "trapping rain water II" (a 2D elevation map)?
A: Push every boundary cell of the grid into a min-heap ordered by height, marking cells visited. Repeatedly pop the lowest boundary cell, and for each unvisited neighbor, the water trapped there is max(0, currentBoundaryHeight - neighborHeight); push the neighbor into the heap with height max(currentBoundaryHeight, neighborHeight) (its new effective wall height) and mark it visited. This is a heap-driven BFS variant of Dijkstra, processing cells in order of the lowest surrounding "water wall," and runs in O(m×n log(m×n)).
Q107. What is the time complexity of checking whether the K smallest elements of a stream have changed after each new insertion, if you use a heap versus resorting?
A: With a bounded max-heap of size K, each new element costs O(log K) to potentially insert and evict, so n insertions total O(n log K). Resorting a maintained list of size K from scratch after every insertion costs O(K log K) per insertion, or O(n × K log K) total — asymptotically far worse whenever insertions are frequent, which is why streaming top-K problems are the textbook use case for a bounded heap rather than repeated sorting.
Q108. Why do interviewers frequently pair heap questions with "explain why this beats sorting" follow-ups?
A: Because a full sort is almost always a valid brute-force fallback for "find the kth/top-K something," and the interesting signal is whether the candidate recognizes that a heap avoids the wasted O(n log n) work of fully ordering elements you don't actually need ordered — you only need the top K, not all n in exact order. Being able to state precisely that a bounded heap gives O(n log k) versus full sort's O(n log n) (a meaningful win when k << n) is what distinguishes a strong answer from one that merely produces a correct but naive solution.
Q109. How would you extend a min-heap to efficiently support "get the median-ranked element" (not just min or max) on demand?
A: A plain heap alone can't do this efficiently — it only exposes the extreme end in O(1). The standard trick is again the two-heap balanced split (as used for streaming medians): with the collection partitioned into a max-heap of the lower half and a min-heap of the upper half kept size-balanced, the "median-ranked" element is always O(1) to read from one of the two roots, while arbitrary other ranks (e.g., 25th percentile) would require a more general order-statistics structure like an order-statistic tree or a Fenwick tree over ranks.
Q110. Summarize the core interview signal that heap and priority queue questions are designed to test.
A: Heap questions test whether a candidate recognizes the recurring pattern "I repeatedly need the current best (min/max) from a changing collection" and reaches for a structure offering O(log n) insert/extract instead of O(n log n) re-sorting or O(n) linear scanning. They also test API fluency (java.util.PriorityQueue's comparator-driven ordering, its O(n) search/O(log n) insert/extract split) and awareness of the structure's limits — no efficient arbitrary search, no efficient decrease-key without an indexed variant, and no full ordering guarantee beyond the root.
Post a Comment
Add