Heaps & priority queues

The problem a heap exists to solve

If you need the minimum (or maximum) value once, scan the array — O(n). If you need it repeatedly, while the data keeps changing, sorting every time is O(n log n) per query — wasteful. A heap gives you the extreme value in O(1) and lets you add or remove in O(log n), which is the sweet spot for "keep asking me for the biggest one" problems.

The one rule: parent beats children

A heap is not sorted, and it's not a BST — a node's left child can be bigger or smaller than its right child, the only guarantee is parent-vs-children. That weaker guarantee is exactly what makes insert and remove-min cheaper than keeping the whole thing sorted.

Sift-up (insert) and sift-down (remove) — the two moves

Insert always adds at the very end of the array, then "bubbles" it up while it's smaller than its parent. Removing the min always takes the last element, drops it at the root, then "sinks" it down while it's bigger than its smallest child. Both are O(log n) because they only ever travel the height of the tree.

class MinHeap {
  #data = [];

  peek() { return this.#data[0]; }
  size() { return this.#data.length; }

  push(val) {
    this.#data.push(val);
    this.#siftUp(this.#data.length - 1);
  }

  pop() {
    const min = this.#data[0];
    const last = this.#data.pop();
    if (this.#data.length > 0) {
      this.#data[0] = last;
      this.#siftDown(0);
    }
    return min;
  }

  #siftUp(i) {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.#data[parent] <= this.#data[i]) break;
      [this.#data[parent], this.#data[i]] = [this.#data[i], this.#data[parent]];
      i = parent;
    }
  }

  #siftDown(i) {
    const n = this.#data.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1, right = 2 * i + 2;
      if (left < n && this.#data[left] < this.#data[smallest]) smallest = left;
      if (right < n && this.#data[right] < this.#data[smallest]) smallest = right;
      if (smallest === i) break;
      [this.#data[i], this.#data[smallest]] = [this.#data[smallest], this.#data[i]];
      i = smallest;
    }
  }
}

One Heap class for every job: a comparator

The MinHeap above hard-codes one decision: < on the stored values. That is enough for plain numbers, but interview problems put pairs in the heap: a (distance, point), a (count, word), an (end time, room). Rewriting the sift loops for every shape is how heap bugs get written. The fix is to pull that one decision out into a function. The heap asks "does a come out before b?" and never looks inside the items itself.

The contract is the same as Array.prototype.sort: a comparator returns a negative number when a must come out first, a positive number when b must, and 0 for a tie. The heap below only ever tests compare(x, y) < 0 ("strictly before") or >= 0, so equal items never swap.

class Heap {
  #data;
  #compare;

  constructor(compare, items = []) {
    this.#compare = compare;
    this.#data = items.slice();
    for (let i = (this.#data.length >> 1) - 1; i >= 0; i--) this.#siftDown(i); // heapify in O(n)
  }

  size() { return this.#data.length; }
  peek() { return this.#data[0]; }

  push(item) {
    this.#data.push(item);
    this.#siftUp(this.#data.length - 1);
  }

  pop() {
    const top = this.#data[0];
    const last = this.#data.pop();
    if (this.#data.length > 0) {
      this.#data[0] = last;
      this.#siftDown(0);
    }
    return top;
  }

  #siftUp(i) {
    const data = this.#data;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.#compare(data[i], data[parent]) >= 0) break; // not strictly better than its parent: stay
      [data[i], data[parent]] = [data[parent], data[i]];
      i = parent;
    }
  }

  #siftDown(i) {
    const data = this.#data;
    const n = data.length;
    while (true) {
      let best = i;
      const left = 2 * i + 1, right = left + 1;
      if (left < n && this.#compare(data[left], data[best]) < 0) best = left;
      if (right < n && this.#compare(data[right], data[best]) < 0) best = right;
      if (best === i) break;
      [data[i], data[best]] = [data[best], data[i]];
      i = best;
    }
  }
}

Two details are worth reading twice. The constructor accepts a starting array and fixes it with the bottom-up loop from the heapify section below, so new Heap(compare, items) costs O(n) rather than n pushes at O(n log n). And it copies the array with slice(), so the caller's array is not reordered behind their back.

Now MinHeap and MaxHeap are one line each. This MinHeap replaces the earlier class, and new MinHeap() works exactly as before. The MaxHeap is the one the MedianFinder below assumes, and it is only the comparator turned around.

class MinHeap extends Heap {
  constructor(items) { super((a, b) => a - b, items); }
}

class MaxHeap extends Heap {
  constructor(items) { super((a, b) => b - a, items); }
}

Everything else in this chapter builds on these three classes. What you put into the heap decides what the comparator looks like:

const byDistance = new Heap((a, b) => a.dist - b.dist); // objects: compare one field
byDistance.push({ node: "A", dist: 7 });
byDistance.push({ node: "B", dist: 2 });
byDistance.pop().node; // "B"

const byCountThenWord = new Heap((a, b) => b[1] - a[1] || (a[0] < b[0] ? -1 : a[0] > b[0] ? 1 : 0)); // arrays: most frequent first, then alphabetical

The last comparator uses || as a tie-break: when the counts are equal b[1] - a[1] is 0, which is falsy, so evaluation falls through to the alphabetical comparison.

The top-K pattern

This is where heaps earn their keep: finding the k largest elements out of n. Sorting everything is O(n log n). A heap does it in O(n log k) — and when k is small relative to n, that's a real win.

// k largest elements — keep a MIN-heap of size k (counter-intuitive but correct)
function kLargest(nums, k) {
  const heap = new MinHeap();
  for (const num of nums) {
    heap.push(num);
    if (heap.size() > k) heap.pop(); // evict the smallest — keep only the top k
  }
  const result = [];
  while (heap.size() > 0) result.push(heap.pop()); // draining a min-heap yields the k largest smallest-first
  return result.reverse();                         // largest first
}

The trick that trips people up: for "k largest," you use a min-heap, not a max-heap — because you want to cheaply evict the smallest of your current top-k candidates the moment a bigger one shows up. The heap's root is always "the next one to kick out," which is the smallest of the keepers.

Dry run: kLargest([3, 1, 5, 9, 2, 7], 3)

Every time the heap tips over size k, whatever just became the new minimum is exactly what leaves — so the heap only ever holds candidates for the answer, never a value that's already been beaten by k bigger ones. It ends holding {5, 7, 9}: the three largest values. Draining the heap with pop() gives 5, 7, 9, and the final reverse() returns [9, 7, 5] as a plain array (an extra O(k log k), no more than the O(n log k) of the loop).

Top-K frequent: a heap, buckets or quickselect

"Return the k most frequent elements" combines two steps. Counting is always the same: one pass with a Map, O(n). (A plain object would turn the numbers 1 and "1" into one key, and a Map keeps them apart.) Choosing the k biggest counts from d distinct values is where the three methods differ, and each one shows a different trade.

Method 1: the size-k heap

This is the pattern from earlier with one change: the entries are [value, count] pairs and the comparator looks at the count. A Map iterates as exactly those pairs, so the entries need no building.

function topKFrequent(nums, k) {
  const counts = new Map();
  for (const x of nums) counts.set(x, (counts.get(x) ?? 0) + 1);
  const heap = new Heap((a, b) => a[1] - b[1]); // [value, count]: the least frequent keeper on top
  for (const entry of counts) {
    heap.push(entry);
    if (heap.size() > k) heap.pop();
  }
  const result = [];
  while (heap.size() > 0) result.push(heap.pop()[0]);
  return result.reverse();
}

topKFrequent([1, 1, 1, 2, 2, 3], 2) counts to {1: 3, 2: 2, 3: 1}. The heap takes [1, 3], then [2, 2]; pushing [3, 1] makes three entries, so the least frequent, [3, 1], is popped. What is left drains as 2 then 1, and the final reverse gives [1, 2]. Cost: O(n) to count, then d pushes and pops on a heap of at most k + 1 entries, O(d log k), so O(n + d log k) overall with O(d) space for the counts.

Method 2: buckets by frequency, O(n)

A count can only be a whole number between 1 and n. That is a small, known range, so you do not need to compare counts at all. Put each value in a bucket numbered by its count, then read the buckets from the highest count down until you have k values.

function topKFrequentBucket(nums, k) {
  const counts = new Map();
  for (const x of nums) counts.set(x, (counts.get(x) ?? 0) + 1);
  const buckets = Array.from({ length: nums.length + 1 }, () => []); // buckets[c] = values that appear c times
  for (const [value, count] of counts) buckets[count].push(value);
  const result = [];
  for (let c = buckets.length - 1; c > 0 && result.length < k; c--) {
    for (const value of buckets[c]) if (result.length < k) result.push(value);
  }
  return result;
}

Counting is O(n), filling the buckets is O(d), and the scan visits n + 1 buckets and at most d values, so the total is O(n) time and O(n) space. The bucket array has n + 1 slots, not n, because a single value can appear n times and then its count is n, which is index n of the array.

Method 3: quickselect on the distinct values

If you only need the top k as a set, you do not need them in order. Partition the distinct values around a random pivot by count, put the higher counts on the left, and keep only the side that contains position k - 1. After the loop, the first k entries are the answer. This is the same quickselect as in the sorting chapter, with counts as the key.

function partitionByCount(items, counts, lo, hi) {
  const pick = lo + Math.floor(Math.random() * (hi - lo + 1));
  [items[pick], items[hi]] = [items[hi], items[pick]];
  const pivot = counts.get(items[hi]);
  let store = lo;
  for (let i = lo; i < hi; i++) {
    if (counts.get(items[i]) > pivot) { // a higher count belongs on the left
      [items[i], items[store]] = [items[store], items[i]];
      store++;
    }
  }
  [items[store], items[hi]] = [items[hi], items[store]];
  return store;
}

function topKFrequentQuickselect(nums, k) {
  const counts = new Map();
  for (const x of nums) counts.set(x, (counts.get(x) ?? 0) + 1);
  const items = [...counts.keys()];
  let lo = 0, hi = items.length - 1;
  while (lo < hi) {
    const p = partitionByCount(items, counts, lo, hi);
    if (p === k - 1) break;
    if (p < k - 1) lo = p + 1;
    else hi = p - 1;
  }
  return items.slice(0, k);
}

On average each partition halves the work, so the total is about O(d), and the worst case is O(d²). The worst case is not exotic here. When every value has the same count, the strict > test never moves anything left, so each partition places just one element. We ran this on 20,000 distinct values that all appeared once, asking for the top 19,999, and the partitions read a count about 200 million times, which is d²/2. The fix is a three-way partition (less, equal, greater), which the sorting chapter covers in Sorting algorithms.

Building a heap from an array in O(n), not O(n log n)

Pushing n elements one at a time costs O(n log n) — each push is O(log n). But if you already have the full array upfront, you can build the heap faster: place all elements as-is, then sift-down starting from the last non-leaf node backward to the root.

function siftDown(arr, i, n) { // the same loop as the class's #siftDown, as a free function
  while (true) {
    let smallest = i;
    const left = 2 * i + 1, right = 2 * i + 2;
    if (left < n && arr[left] < arr[smallest]) smallest = left;
    if (right < n && arr[right] < arr[smallest]) smallest = right;
    if (smallest === i) break;
    [arr[i], arr[smallest]] = [arr[smallest], arr[i]];
    i = smallest;
  }
}

function heapify(arr) {
  const n = arr.length;
  // last non-leaf node is at index Math.floor(n/2) - 1 — every index after that is a leaf
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(arr, i, n);
  }
  return arr;
}

The two-heap pattern — running median of a data stream

A single heap gives you the min or the max. Finding the median of a growing stream needs both at once — the classic trick is to split the data across two heaps that meet in the middle.

class MedianFinder {
  #small = new MaxHeap(); // same MinHeap code, comparisons flipped — holds the smaller half
  #large = new MinHeap(); // holds the larger half

  addNum(num) {
    this.#small.push(num);
    this.#large.push(this.#small.pop()); // always route through #small first, then rebalance

    if (this.#small.size() < this.#large.size()) {
      this.#small.push(this.#large.pop()); // keep #small equal-or-one-more than #large
    }
  }

  findMedian() {
    if (this.#small.size() > this.#large.size()) return this.#small.peek();
    return (this.#small.peek() + this.#large.peek()) / 2;
  }
}

Every insert is O(log n), and reading the median is O(1) — compare that to re-sorting on every insert (O(n log n) each time) or inserting into a sorted array (O(n) shifting each time). The two-heap split is what makes a streaming median tractable at all.

See it sink

Watch the last element take the root's place and then sink. It only ever follows the smaller child, so it touches one node per level — that is the log n.

Merge K sorted lists, and the K smallest pairs

You have k lists, each already sorted, and you want one sorted list. Two naive plans fail. Concatenating and sorting costs O(N log N) for N total elements and ignores that the lists are sorted. Merging them one at a time into a growing result copies that result again at every step, so with k lists of equal length it costs O(N · k).

Look at what the next output must be. It is the smallest element not yet output. Every list is sorted, so the smallest unused element of a list is its front. So the next output is the smallest of at most k fronts. That is a min-heap question. Keep the heap holding exactly one front per non-empty list. Pop the smallest, output it, and push the next element of the list it came from. The heap never holds more than k entries, so each of the N pops and pushes costs O(log k), and the whole merge is O(N log k) time with O(k) extra space beyond the output.

function mergeKSorted(lists) {
  const heap = new Heap((a, b) => a[0] - b[0]); // entry = [value, which list, index in that list]
  lists.forEach((list, i) => {
    if (list.length > 0) heap.push([list[0], i, 0]);
  });
  const merged = [];
  while (heap.size() > 0) {
    const [value, i, j] = heap.pop();
    merged.push(value);
    if (j + 1 < lists[i].length) heap.push([lists[i][j + 1], i, j + 1]);
  }
  return merged;
}

Each heap entry is a tuple [value, which list, position in that list]: the value to compare, and the two numbers needed to find the successor. Without the list index you could not know where to refill from.

Dry run: mergeKSorted([[1, 4, 7], [2, 5], [3, 6, 9]])

The heap shrinks from three entries to none as lists run out. It never grows past three, which is k. That bound is what turns log N into log k.

The linked-list version

The classic interview form gives the lists as linked lists. The heap can then hold the nodes themselves, because a node already knows its successor, and the comparator reads val. The merged list is built by re-linking the existing nodes, so nothing is copied.

function mergeKLists(lists) {
  const heap = new Heap((a, b) => a.val - b.val); // the entries are the list nodes themselves
  for (const head of lists) if (head !== null) heap.push(head);
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (heap.size() > 0) {
    const node = heap.pop();
    tail.next = node;
    tail = node;
    if (node.next !== null) heap.push(node.next);
  }
  return dummy.next;
}

Two edge cases explain the guards. A list can be empty, which here is null as a head, and an empty head must not be pushed, since the comparator would read null.val. And lists itself can be empty, in which case the heap never fills and dummy.next is null, the right answer. The dummy node is the usual trick from the linked-list chapter, so that attaching the first node is not a special case.

K pairs with the smallest sums

Given two sorted arrays nums1 and nums2, find the k pairs (u, v), with u from the first and v from the second, that have the smallest sums. There are m · n pairs, so listing them all and sorting is far too much when k is small.

Look at it as k-way merge in disguise. For each i the pairs (nums1[i], nums2[0]), (nums1[i], nums2[1]), ... form a list whose sums are already sorted, because nums2 is sorted. That is m sorted lists, generated on demand. So seed the heap with the front of each list, which is the pair (i, 0), and pop and refill exactly as before: popping (i, j) pushes (i, j + 1).

function kSmallestPairs(nums1, nums2, k) {
  const result = [];
  if (nums1.length === 0 || nums2.length === 0) return result;
  const heap = new Heap((a, b) => a[0] - b[0]); // entry = [sum, i, j]
  for (let i = 0; i < Math.min(nums1.length, k); i++) heap.push([nums1[i] + nums2[0], i, 0]);
  while (result.length < k && heap.size() > 0) {
    const [, i, j] = heap.pop();
    result.push([nums1[i], nums2[j]]);
    if (j + 1 < nums2.length) heap.push([nums1[i] + nums2[j + 1], i, j + 1]);
  }
  return result;
}

Two things keep this cheap. Only the first min(m, k) rows are seeded: any pair in row k or later has a sum at least as large as the front pairs of the k rows before it, so those k pairs always beat it (or tie with it) and it can be skipped. And no visited set is needed. In the merge view each pair (i, j) is pushed by exactly one event, the pop of (i, j - 1) (or the seeding, for j = 0), so no pair is ever pushed twice.

Dry run: kSmallestPairs([1, 7, 11], [2, 4, 6], 3)

The loop stops at three results. Cost: the heap holds at most min(m, k) entries, there are at most k pops, and each pop does one push, so it is O(k log min(m, k)). The other arrays in this family reuse the same engine: "k-th smallest in a sorted matrix" is k-way merge over the rows, and "smallest range covering one number from each of k lists" is the same heap plus a running maximum. Both are practice problems for this chapter.

Greedy with a heap: the best option available right now

A large family of interview problems has this shape. You walk through time (or through a sorted list), options become available as you go, and at each decision you want the best option among those available. "Best of what is available, and the set keeps changing" is the sentence that calls for a heap. The heap is used in two ways, and naming the way tells you what to push and when to pop:

• Release, then take the best. Sort the options by when they become available. As time passes, move each newly available option into the heap, then pop the best one to use it (IPO, task scheduler, reorganize string).
• Take now, undo the worst later. Make the cheap choice for everything, keep the choices in a heap, and when you run out of budget, reverse the least valuable choice in the heap (furthest building).

Meeting rooms II: how many rooms at once

Given meeting intervals, find the fewest rooms that fit them all. Sort by start time and walk through the meetings. A new meeting needs a room. It can reuse a room only if that room's meeting has already ended, and the room most likely to be free is the one whose meeting ends earliest. So the heap holds the end time of the current meeting in each room in use, and the root is the earliest end. If the root is at or before the new start, reuse that room (pop it and push the new end). Otherwise a room has to be added (push only).

function minMeetingRooms(intervals) {
  const sorted = intervals.slice().sort((a, b) => a[0] - b[0]);
  const ends = new MinHeap(); // end time of the latest meeting in each room in use
  for (const [start, end] of sorted) {
    if (ends.size() > 0 && ends.peek() <= start) ends.pop(); // that room is free: reuse it
    ends.push(end);
  }
  return ends.size();
}

Dry run: [[0, 30], [5, 10], [12, 25], [15, 20]]

The answer is the final heap size, 3. The size only ever grows when no room was free, because a reuse pops and pushes in the same step, so the size at the end is the largest number of rooms ever needed at once. Cost: O(n log n) for the sort and O(n log n) for the heap. Watch the boundary: peek() <= start treats a meeting that ends at 10 and one that starts at 10 as back-to-back, which is what the usual statement of the problem means. The same answer also comes from the sweep-line method in Intervals.

Connect sticks: always merge the two shortest

Joining two sticks costs the sum of their lengths, and you must end with one stick. Every stick that takes part in a merge has its length paid again in every later merge that includes the merged result. So lengths merged early are paid for many times, and lengths merged last only once. To pay the least, merge the shortest sticks first and keep the long ones for the end. That is Huffman's idea.

function connectSticks(sticks) {
  const heap = new MinHeap(sticks);
  let cost = 0;
  while (heap.size() > 1) {
    const merged = heap.pop() + heap.pop();
    cost += merged;
    heap.push(merged);
  }
  return cost;
}

connectSticks([2, 4, 3]): take 2 and 3, cost 5, push 5 to get {4, 5}; take 4 and 5, cost 9; the total is 14. Merging 3 and 4 first would cost 7 and then 9 for 16, so the greedy choice does matter. Cost: each of the n - 1 merges does two pops and one push, so O(n log n). We checked it against trying every merge order on random inputs of up to six sticks.

Furthest building you can reach: ladders for the biggest climbs

You walk across buildings. A drop or a flat step is free. A climb of d costs d bricks or one ladder, and a ladder covers any height. How far can you get? The decision for a climb is hard to make in the moment, because you do not know yet what lies ahead. So delay it. Give every climb a ladder as you meet it, and put its height in a min-heap. Once there are more laddered climbs than ladders, one of them has to be paid in bricks. The cheapest one to pay in bricks is the smallest laddered climb, which is the heap's root. Pop it and pay for it. If the bricks go below zero, you cannot cross the step you were on.

function furthestBuilding(heights, bricks, ladders) {
  const onLadders = new MinHeap(); // the climbs currently given a ladder
  for (let i = 0; i < heights.length - 1; i++) {
    const climb = heights[i + 1] - heights[i];
    if (climb <= 0) continue;
    onLadders.push(climb);
    if (onLadders.size() > ladders) {
      bricks -= onLadders.pop(); // the smallest laddered climb is paid in bricks instead
      if (bricks < 0) return i;
    }
  }
  return heights.length - 1;
}

Dry run: heights [4, 2, 7, 6, 9, 14, 12], 5 bricks, 1 ladder

The loop stops at index 4 (the climb from building 4 to building 5 fails), so the answer is 4. The invariant that makes it correct: after each step, the heap holds exactly the largest climbs seen so far (as many as there are ladders), and every other climb has been paid in bricks. Ladders on the biggest climbs and bricks on the rest is the cheapest way to cover a prefix, so the first step where the bricks run out is the furthest reachable. Cost: O(n log L) for L ladders. We checked it against a search over every ladder-or-bricks choice on random inputs.

IPO: start the most profitable project you can afford

You have capital w and may start at most k projects. Each project needs some capital to start and adds its profit to your capital when finished. The capital you hold only grows, so a project that is affordable now stays affordable. Sort projects by the capital they need. Before each round, move every project you can now afford into a max-heap of profits, then start the one with the largest profit. Starting the largest affordable profit leaves you with the most capital after this round, and more capital never makes a project harder to afford.

function findMaximizedCapital(k, w, profits, capital) {
  const projects = profits.map((p, i) => [capital[i], p]).sort((a, b) => a[0] - b[0]);
  const affordable = new MaxHeap(); // profits of the projects we can start right now
  let next = 0;
  for (let round = 0; round < k; round++) {
    while (next < projects.length && projects[next][0] <= w) {
      affordable.push(projects[next][1]);
      next++;
    }
    if (affordable.size() === 0) break;
    w += affordable.pop();
  }
  return w;
}

findMaximizedCapital(2, 0, [1, 2, 3], [0, 1, 1]): with 0 capital only the first project is affordable, so profit 1 is taken and capital becomes 1. Now both other projects are affordable, the heap holds {2, 3}, and 3 is taken for a final capital of 4. Cost: O(n log n) for the sort plus at most n pushes and k pops, O((n + k) log n). The break matters: if nothing is affordable the capital cannot change any more, so further rounds would only repeat. We checked the function against trying every project order, on random inputs with profits of zero or more, as the problem states.

Task scheduler: run the task with the most left

Tasks are labelled with letters. One task runs per time unit, and two runs of the same letter must have at least n other units between them. Find the shortest time to finish them all (idle units count). The greedy move is to run, at each unit, whichever allowed task has the most runs left: the task with the longest remaining chain also has the most forced waiting ahead of it, so it should not be left for last. After a task runs, it sleeps for n units and cannot return to the heap until its cooldown ends. So there are two containers: a max-heap of tasks that may run, and a queue of sleeping ones in the order they went to sleep.

function leastInterval(tasks, n) {
  const counts = new Map();
  for (const t of tasks) counts.set(t, (counts.get(t) ?? 0) + 1);
  const ready = new MaxHeap([...counts.values()]); // remaining runs of each task that may run now
  const cooling = []; // [time it may run again, remaining runs], in the order they went to sleep
  let time = 0;
  while (ready.size() > 0 || cooling.length > 0) {
    time++;
    if (ready.size() > 0) {
      const left = ready.pop() - 1;
      if (left > 0) cooling.push([time + n, left]);
    }
    if (cooling.length > 0 && cooling[0][0] === time) ready.push(cooling.shift()[1]);
  }
  return time;
}

Dry run: tasks A A A B B B, n = 2

The answer is 8 (A B idle A B idle A B). Notice the heap simulation advances one time unit per loop turn, so it costs O(answer · log u) for u distinct letters. That is fine for small n but not when n is huge: two tasks A A with n = 1000000000 would make about a billion turns. The closed form avoids that: with m the highest count and c the number of letters that reach it, the answer is max(tasks.length, (m - 1) * (n + 1) + c), which takes O(T) for T tasks. We compared the simulation, the formula and an exhaustive search on random inputs and they agree. The heap version is still worth knowing because it extends to "also print the schedule".

Reorganize string: never place the same letter twice in a row

Rearrange a string so that no two adjacent characters are equal, or say it is impossible. Impossible exactly when some letter appears more than ceil(n / 2) times, because even placing it in every other slot needs that many. Otherwise build the answer left to right with a max-heap of [letter, copies left]. At each step place the letter with the most copies left, except that the letter you placed one step ago must sit this step out. Pop the top letter, put it in the result, and only then return the previous letter to the heap. The new letter is held back and goes into the heap on the next turn.

function reorganizeString(s) {
  const counts = new Map();
  for (const ch of s) counts.set(ch, (counts.get(ch) ?? 0) + 1);
  const heap = new Heap((a, b) => b[1] - a[1]); // [letter, copies left], the most copies on top
  for (const entry of counts) heap.push(entry);
  let result = "";
  let resting = null; // the letter placed last step: it may not go first this step
  while (heap.size() > 0 || resting !== null) {
    if (heap.size() === 0) return ""; // only the resting letter is left, and it would touch itself
    const [ch, left] = heap.pop();
    result += ch;
    if (resting !== null) heap.push(resting);
    resting = left > 1 ? [ch, left - 1] : null;
  }
  return result;
}

Dry run: reorganizeString("aaabbc")

Adjacent letters are never equal, because a letter is held out for one turn after it is placed. The only way to get stuck is the heap being empty while a letter is still resting, which means that letter has more copies than the others can separate, and the function returns "". Cost: n pops and pushes on a heap of at most u letters, so O(n log u). We checked it on random strings of up to seven letters against trying every ordering: it succeeds exactly when an ordering exists, and then the result is a valid rearrangement.

Lazy deletion and the sliding-window median

A heap is built for removing the top. Removing an arbitrary element is a different matter: finding it takes O(n), because a heap says nothing about where a given value sits. Some problems still need it. The median of every window of size k slides along an array: each step adds one number and removes the number that leaves the window, which may be anywhere in either heap.

The fix is lazy deletion. Do not remove it. Write down that one copy of that value is now dead, and leave it where it is. Dead entries only matter when they reach the top, so whenever the top of a heap is dead, pop it for real and cross it off the list. The heap always holds a mix of live and dead entries. What changes are three rules:

• Count live entries yourself. heap.size() includes dead entries, so the two-heap balance has to use separate live counters.
• Keep both tops live. After every change, prune the top of any heap that might now hold a dead entry. Then peek() is always trustworthy.
• Record deaths by value, with a count. Equal numbers are interchangeable, so a Map from value to "copies owed" is enough, and it handles duplicates.

function medianSlidingWindow(nums, k) {
  const small = new MaxHeap(); // lower half
  const large = new MinHeap(); // upper half
  const owed = new Map(); // value -> how many copies are dead but still sitting in a heap
  let smallLive = 0, largeLive = 0;

  const prune = (heap) => {
    while (heap.size() > 0 && (owed.get(heap.peek()) ?? 0) > 0) {
      owed.set(heap.peek(), owed.get(heap.peek()) - 1);
      heap.pop();
    }
  };
  const rebalance = () => {
    if (smallLive > largeLive + 1) {
      large.push(small.pop());
      smallLive--; largeLive++;
      prune(small);
    } else if (smallLive < largeLive) {
      small.push(large.pop());
      largeLive--; smallLive++;
      prune(large);
    }
  };
  const add = (x) => {
    if (smallLive === 0 || x <= small.peek()) { small.push(x); smallLive++; }
    else { large.push(x); largeLive++; }
    rebalance();
  };
  const remove = (x) => {
    owed.set(x, (owed.get(x) ?? 0) + 1);
    if (x <= small.peek()) {
      smallLive--;
      if (x === small.peek()) prune(small);
    } else {
      largeLive--;
      if (x === large.peek()) prune(large);
    }
    rebalance();
  };

  const medians = [];
  for (let i = 0; i < nums.length; i++) {
    add(nums[i]);
    if (i >= k) remove(nums[i - k]);
    if (i >= k - 1) medians.push(k % 2 === 1 ? small.peek() : (small.peek() + large.peek()) / 2);
  }
  return medians;
}

To decide which half a leaving number belongs to, the code uses the same test as insertion: x <= small.peek(), "does it belong to the lower half?". That is correct even when an equal value also sits in the other heap, since equal values are interchangeable and only the live counts matter.

Dry run: medianSlidingWindow([2, 8, 4, 5], 3)

The last row shows the idea at work. The number 2 left the window, but it sits at the bottom of the lower heap, not at its top, so it stays as a dead entry and is only recorded in the owed map. The live counts show the lower half is now one element too short, so the upper heap's smallest, 5, moves down. The lower heap's top is 5 (live), and the window [8, 4, 5] has median 5. The earlier window [2, 8, 4] has median 4.

Cost: every element is pushed once on arrival, and each rebalancing moves at most one element, so there are O(n) pushes and pops in all, each O(log of the heap size). The heaps can contain buried dead entries, so their size is bounded by n rather than k, and the total is O(n log n) time with O(n) space in the worst case. A structure that can delete by value (an ordered set, or a heap that tracks each item's position) brings it to O(n log k).

The same trick shows up wherever a priority can change: instead of updating an entry's priority in place, push a new entry and skip stale ones when they surface. Dijkstra's algorithm does exactly that, as you will see in Advanced graph algorithms. For small windows, the plain alternative is a sorted array of the window with a binary search for each insert and delete, O(k) per step and much less to get wrong.

Heapsort, and what each operation costs

The heap gives you a sorting algorithm for free. Build a max-heap in place. Its root is the largest element, so swap it with the last slot of the heap range, which puts it in its final sorted position. Shrink the heap range by one, sift the new root down to restore the heap, and repeat. The sorted tail grows from the right while the heap shrinks from the right.

function siftDownMax(arr, i, n) {
  while (true) {
    let largest = i;
    const left = 2 * i + 1, right = left + 1;
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest === i) break;
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    i = largest;
  }
}

function heapSort(arr) {
  const n = arr.length;
  for (let i = (n >> 1) - 1; i >= 0; i--) siftDownMax(arr, i, n); // 1. build a max-heap in place
  for (let end = n - 1; end > 0; end--) {
    [arr[0], arr[end]] = [arr[end], arr[0]]; // 2. the maximum goes to its final slot
    siftDownMax(arr, 0, end); // the heap is now arr[0..end-1]
  }
  return arr;
}

Dry run: heapSort([4, 10, 3, 5, 1])

A single element is already in place, so the loop stops and the whole array is [1, 3, 4, 5, 10]. Cost: building the heap is O(n), as derived earlier, and then n - 1 sift-downs each cost at most O(log n), so the worst case is O(n log n) with O(1) extra space, because everything happens inside the one array. It is not stable: sorting the records {k:2, id:"a"}, {k:2, id:"b"}, {k:1, id:"c"} by k with this code gave c, b, a, so the two records with key 2 swapped places. The built-in Array.prototype.sort is required by the language specification to be stable, so use it when equal keys must keep their order.

What every heap operation costs

Three selection tools come out of this. For the k-th largest of n numbers: a size-k heap is O(n log k) and works on a stream; heapifying everything and popping k times is O(n + k log n), which wins when k is small and the data is all there; quickselect is O(n) on average with an O(n²) worst case and no extra structure. Sorting is O(n log n) and the simplest of all. Which is right depends on whether the data streams, whether you need the elements in order, and how large k is compared with n.

Recognizing it in an unseen problem

• "Top K," "k-th largest/smallest," "k closest points"
• Merging k sorted lists/arrays — a heap tracks "the smallest unmerged element" across all of them
• You need repeated access to a min/max while the data set keeps changing (a scheduler, a running median)
• "Running median," "median of a stream" → the two-heap pattern specifically
• A brute force would re-sort after every update — that's the tell a heap should replace it
• "K smallest pairs," "k-th smallest in a sorted matrix" — a k-way merge over lists you generate as you go, not ones handed to you
• "Fewest rooms," "furthest you can reach," "maximize capital," "task with the most left": a greedy that takes the best option among those available right now
• A sliding window where the median or extreme is needed and old items must leave the structure: two heaps with lazy deletion
• "Top K frequent": count first, then choose between a size-k heap, buckets by count and quickselect