Use heap to always pick the optimal element greedily
When to useTask scheduler, reorganize string, connect ropes, minimum cost merge
iterative
Connect Ropes
connect_ropesFind The Highest Profit
find_the_highest_profitFive Star Seller
five_star_sellersMerge K Sorted Lists
merge_k_sorted_listsMultiprocessor System
multiprocessor_systemReorganize String
reorganize_stringKth Smallest Element in a Sorted Matrix
kth_smallest_element_in_a_sorted_matrixLongest String Without 3 Consecutive Characters
longest_string_without_3_consecutive_charactersMeeting Rooms IImedium
meeting_rooms_ii · no slotsINITIALIZE
insert all elements into heap (max or min)
const heap = new MinHeap();for (const r of ropes) heap.push(r);let cost = 0;
const heap = new MaxHeap();for (const inv of inventories) heap.push(inv);let profit = 0;
const heap = new MaxHeap(); // keyed by marginal gainlet sum = 0;for (const [five, total] of productRatings) {sum += five / total;heap.push([gain(five, total), five, total]);}
const heap = new MinHeap();for (let i = 0; i < lists.length; i++) {if (lists[i].length > 0) heap.push([lists[i][0], i, 0]);}const result = [];
const heap = new MaxHeap();for (const power of processorPower) heap.push(power);let hours = 0;let remaining = tasks;
const counts = new Map();for (const ch of s) counts.set(ch, (counts.get(ch) ?? 0) + 1);const heap = new MinHeap((a, b) => b[1] - a[1]);for (const [ch, c] of counts) {if (c > Math.ceil(s.length / 2)) return '';heap.push([ch, c]);}let result = ''; let prev = null;
const heap = new MinHeap();heap.push({ priority: matrix[0][0], row: 0, col: 0 });const columnTop = Array(n).fill(0);const rowFirst = Array(n).fill(0);
const heap = new MaxHeap();if (a > 0) heap.push([a, 'a']);if (b > 0) heap.push([b, 'b']);if (c > 0) heap.push([c, 'c']);let result = '';
—
TRAVERSE
while heap not empty (or size > 1)
while (heap.size() > 1) {
for (let i = 0; i < order; i++) {
while (sum < target) {
while (heap.size() > 0) {
while (remaining > 0) {
while (heap.size() > 0) {
while (k > 1) {
while (heap.size() > 0) {
—
pop optimal
pop optimal element(s) from heap
const a = heap.pop();const b = heap.pop();
const top = heap.pop();
const [, five, total] = heap.pop();
const [value, listIndex, elemIndex] = heap.pop();
const top = heap.pop();
const [ch, c] = heap.pop();
k--;const { row, col } = heap.pop();
const [count1, ch1] = heap.pop();
—
[COMPUTE]
compute step contribution to result
cost += a + b;
profit += top;
sum += gain(five, total);needed++;
result.push(value);
remaining -= top;hours += 1;
result += ch;
// unlock right neighbor if its column frontier has reached this rowif (col + 1 < n && columnTop[col + 1] === row)heap.push({ priority: matrix[row][col+1], row, col: col+1 });// unlock down neighbor if its row frontier has reached this colif (row + 1 < n && rowFirst[row + 1] === col)heap.push({ priority: matrix[row+1][col], row: row+1, col });rowFirst[row] = col + 1;columnTop[col] = row + 1;
if (last two chars === ch1) {// pop second-best, place it instead, push ch1 backconst [count2, ch2] = heap.pop();result += ch2;heap.push([count2 - 1, ch2]);heap.push([count1, ch1]);} else {result += ch1;heap.push([count1 - 1, ch1]);}
—
reinsert
push back any modified element if applicable
heap.push(a + b);
heap.push(top - 1);
heap.push([gain(five+1, total+1), five+1, total+1]);
if (elemIndex + 1 < lists[listIndex].length)heap.push([lists[listIndex][elemIndex + 1], listIndex, elemIndex + 1]);
heap.push(Math.floor(top / 2));
if (prev !== null && prev[1] > 0) heap.push(prev);prev = [ch, c - 1];
—
—
—
RETURN
return result
return cost;
return profit;
return needed;
return result;
return hours;
return result;
return heap.peek().priority;
return result;
—