Java solutions for heap and greedy problems — the k-th largest element, top-K frequent elements, merging K sorted arrays, task scheduler, reorganizing a string, Huffman coding, the IPO problem, meeting rooms II, fractional knapsack, gas station, minimum platforms, connecting ropes at minimum cost, the median from a data stream, the smallest range covering K lists, and the skyline problem.
Published September 25, 2026
PriorityQueue in Java, a min-heap by default) answer "repeatedly give me the smallest or largest" in O(log n) per operation. Use a size-k heap for top-K problems (O(n log k)), and two heaps for medians.Learn it in depth → Top K Elements
Short answer:
(Practice)
int findKthLargest(int[] a, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : a) { pq.offer(x); if (pq.size() > k) pq.poll(); }
return pq.peek();
}
Short answer: Count the frequencies in a HashMap, then either:
int[] topKFrequent(int[] a, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : a) freq.merge(x, 1, Integer::sum);
List<Integer>[] buckets = new List[a.length + 1];
freq.forEach((x, f) -> (buckets[f] == null ? buckets[f] = new ArrayList<>() : buckets[f]).add(x));
int[] res = new int[k]; int i = 0;
for (int f = a.length; f > 0 && i < k; f--) if (buckets[f] != null) for (int x : buckets[f]) if (i < k) res[i++] = x;
return res;
}
Short answer: Use a min-heap of (value, arrayIndex, elementIndex), seeded with the first element of each array. Pop the smallest, and push the next element from the same array. O(N log K).
List<Integer> mergeKSorted(int[][] arrays) {
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(e -> arrays[e[0]][e[1]]));
for (int i = 0; i < arrays.length; i++) if (arrays[i].length > 0) pq.add(new int[]{i, 0});
List<Integer> out = new ArrayList<>();
while (!pq.isEmpty()) {
int[] e = pq.poll(); out.add(arrays[e[0]][e[1]]);
if (e[1] + 1 < arrays[e[0]].length) pq.add(new int[]{e[0], e[1] + 1});
}
return out;
}
Short answer: Use the formula:
maxF be the highest task frequency, and countMax the number of tasks with that frequency.max(tasks.length, (maxF - 1) * (n + 1) + countMax): the most frequent tasks define the frames, and the idle slots fill the gaps.O(n). (Simulation with a max-heap plus a cooldown queue also works, and returns the actual schedule.)
int leastInterval(char[] tasks, int n) {
int[] f = new int[26]; for (char t : tasks) f[t - 'A']++;
int maxF = Arrays.stream(f).max().getAsInt();
int countMax = (int) Arrays.stream(f).filter(x -> x == maxF).count();
return Math.max(tasks.length, (maxF - 1) * (n + 1) + countMax);
}
Short answer: If any character appears more than (n+1)/2 times, it's impossible. Otherwise, use a max-heap by count: repeatedly take the two most frequent characters and append them, then push them back with decremented counts. O(n log 26). (Alternative: place the most frequent character at the even indices, then fill the rest.)
String reorganizeString(String s) {
int[] cnt = new int[26]; for (char c : s.toCharArray()) cnt[c - 'a']++;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
for (int i = 0; i < 26; i++) if (cnt[i] > 0) {
if (cnt[i] > (s.length() + 1) / 2) return "";
pq.add(new int[]{i, cnt[i]});
}
StringBuilder sb = new StringBuilder();
while (pq.size() >= 2) {
int[] a = pq.poll(), b = pq.poll();
sb.append((char) ('a' + a[0])).append((char) ('a' + b[0]));
if (--a[1] > 0) pq.add(a); if (--b[1] > 0) pq.add(b);
}
if (!pq.isEmpty()) sb.append((char) ('a' + pq.poll()[0]));
return sb.toString();
}
Short answer: Both use the same greedy: repeatedly combine the two smallest items (with a min-heap), and push back their sum.
O(n log n). Merging the smallest first is optimal, because small items then get added into the most merges.
long connectRopes(int[] ropes) {
PriorityQueue<Long> pq = new PriorityQueue<>();
for (int r : ropes) pq.add((long) r);
long cost = 0;
while (pq.size() > 1) { long s = pq.poll() + pq.poll(); cost += s; pq.add(s); }
return cost;
}
record HNode(char ch, int freq, HNode left, HNode right) {}
Map<Character, String> huffman(Map<Character, Integer> freq) {
PriorityQueue<HNode> pq = new PriorityQueue<>(Comparator.comparingInt(HNode::freq));
freq.forEach((c, f) -> pq.add(new HNode(c, f, null, null)));
while (pq.size() > 1) { HNode a = pq.poll(), b = pq.poll(); pq.add(new HNode('\0', a.freq() + b.freq(), a, b)); }
Map<Character, String> codes = new HashMap<>();
assign(pq.poll(), "", codes);
return codes;
}
void assign(HNode n, String code, Map<Character, String> codes) {
if (n == null) return;
if (n.left() == null && n.right() == null) { codes.put(n.ch(), code.isEmpty() ? "0" : code); return; }
assign(n.left(), code + "0", codes); assign(n.right(), code + "1", codes);
}
Short answer: Sort the projects by required capital. Repeat k times:
O(n log n). The greedy works because taking the largest affordable profit only ever increases what you can afford later.
int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
Integer[] idx = new Integer[profits.length];
for (int i = 0; i < idx.length; i++) idx[i] = i;
Arrays.sort(idx, Comparator.comparingInt(i -> capital[i]));
PriorityQueue<Integer> best = new PriorityQueue<>(Collections.reverseOrder());
for (int j = 0, round = 0; round < k; round++) {
while (j < idx.length && capital[idx[j]] <= w) best.add(profits[idx[j++]]);
if (best.isEmpty()) break;
w += best.poll();
}
return w;
}
Short answer: This is the maximum number of overlapping intervals:
end ≤ start). The heap's maximum size is the answer;O(n log n). (Meeting Rooms II)
int minMeetingRooms(int[][] iv) {
int n = iv.length; int[] s = new int[n], e = new int[n];
for (int i = 0; i < n; i++) { s[i] = iv[i][0]; e[i] = iv[i][1]; }
Arrays.sort(s); Arrays.sort(e);
int rooms = 0, best = 0;
for (int i = 0, j = 0; i < n; i++) {
while (j < n && e[j] <= s[i]) { j++; rooms--; } // for platforms, use < if dep == arr needs 2 platforms
best = Math.max(best, ++rooms);
}
return best;
}
Short answer: Greedy by value per unit of weight: sort by value/weight descending; take whole items while they fit, then a fraction of the next one. O(n log n). Greedy is optimal here (items are divisible); for 0/1 knapsack it isn't, so you need DP.
double fractionalKnapsack(int[] wt, int[] val, int cap) {
Integer[] idx = new Integer[wt.length];
for (int i = 0; i < idx.length; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> Double.compare((double) val[b] / wt[b], (double) val[a] / wt[a]));
double total = 0;
for (int i : idx) {
if (cap == 0) break;
int take = Math.min(wt[i], cap);
total += (double) val[i] * take / wt[i]; cap -= take;
}
return total;
}
Short answer: If the total gas is at least the total cost, a solution exists. Scan once; whenever the running tank goes negative at i, no start in [start..i] can work (they all reach i with even less fuel), so restart at i+1. O(n). (The full code is in the array-problems lesson.) (Gas Station)
int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
total += gas[i] - cost[i]; tank += gas[i] - cost[i];
if (tank < 0) { start = i + 1; tank = 0; }
}
return total >= 0 ? start : -1;
}
Short answer: Use two heaps: a max-heap for the lower half and a min-heap for the upper half, balanced so the lower half has the same size, or one more. The median is the top of the lower half, or the average of both tops. addNum is O(log n); findMedian is O(1). (Practice)
class MedianFinder {
private final PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder()), hi = new PriorityQueue<>();
public void addNum(int x) {
lo.add(x); hi.add(lo.poll()); // move the largest of lo to hi
if (hi.size() > lo.size()) lo.add(hi.poll()); // rebalance
}
public double findMedian() {
return lo.size() > hi.size() ? lo.peek() : ((double) lo.peek() + hi.peek()) / 2.0;
}
}
Short answer: Put one element from each list in a min-heap, and track the current maximum. The range [heapMin, curMax] covers all the lists. Pop the minimum, and advance in its list (updating the maximum). Stop when any list is exhausted. O(N log K).
int[] smallestRange(List<List<Integer>> lists) {
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(e -> lists.get(e[0]).get(e[1])));
int max = Integer.MIN_VALUE;
for (int i = 0; i < lists.size(); i++) { pq.add(new int[]{i, 0}); max = Math.max(max, lists.get(i).get(0)); }
int[] best = {0, Integer.MAX_VALUE};
while (true) {
int[] e = pq.poll(); int min = lists.get(e[0]).get(e[1]);
if ((long) max - min < (long) best[1] - best[0]) best = new int[]{min, max};
if (e[1] + 1 == lists.get(e[0]).size()) return best;
int next = lists.get(e[0]).get(e[1] + 1);
max = Math.max(max, next); pq.add(new int[]{e[0], e[1] + 1});
}
}
Short answer: Sweep line plus a max-heap of the active heights:
(x, -h) and an end event (x, h). Sort by x, with starts before ends; taller starts first, and shorter ends first.TreeMap<height, count>, for O(log n) removal).(x, newMax).O(n log n).
List<List<Integer>> getSkyline(int[][] buildings) {
List<int[]> events = new ArrayList<>();
for (int[] b : buildings) { events.add(new int[]{b[0], -b[2]}); events.add(new int[]{b[1], b[2]}); }
events.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
TreeMap<Integer, Integer> heights = new TreeMap<>(Map.of(0, 1));
List<List<Integer>> res = new ArrayList<>(); int prev = 0;
for (int[] e : events) {
if (e[1] < 0) heights.merge(-e[1], 1, Integer::sum);
else if (heights.merge(e[1], -1, Integer::sum) == 0) heights.remove(e[1]);
int cur = heights.lastKey();
if (cur != prev) { res.add(List.of(e[0], cur)); prev = cur; }
}
return res;
}
Q: Why does PriorityQueue.remove(Object) hurt performance?
A: It's a linear search, O(n), followed by an O(log n) sift. For frequent arbitrary removals, use a TreeMap of counts, an indexed heap, or lazy deletion.
Q: How do you create a max-heap in Java?
A: new PriorityQueue<>(Collections.reverseOrder()), or with a comparator such as (a, b) -> Integer.compare(b, a). Avoid b - a, which can overflow for large or negative values.
Q: How do you prove a greedy algorithm is correct? A: Usually with an exchange argument: take any optimal solution that differs from the greedy one, and show that swapping in the greedy choice doesn't make it worse. Or show that greedy "stays ahead" at every step.
Q: What's the complexity of building a heap from n elements?
A: O(n) with bottom-up heapify (new PriorityQueue<>(collection) does this), compared with O(n log n) for n individual inserts.