Heaps and Priority Queues

The root is best, the rest need not be sorted

For a zero-indexed array, parent(i) is floor((i-1)/2), with children 2i+1 and 2i+2. A comparator returning a negative number means its first argument has higher priority.

Insertion appends a value and moves it upward until its parent is no worse. Extraction replaces the root with the last value and moves it downward toward the better child. A complete binary tree has logarithmic height, bounding both repairs.

Heap, sorting, or selection?

A comparator-driven binary heap

This template uses built-in JavaScript only. Empty peek and pop return undefined. Equal priorities may be returned in any order; add a secondary key if your problem requires deterministic ties.

class Heap {
  constructor(compare = (a, b) => a - b) {
    this.items = [];
    this.compare = compare;
  }

  get size() { return this.items.length; }
  peek() { return this.items[0]; }

  push(value) {
    const items = this.items;
    items.push(value);
    let index = items.length - 1;
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.compare(items[index], items[parent]) >= 0) break;
      [items[index], items[parent]] = [items[parent], items[index]];
      index = parent;
    }
  }

  pop() {
    const items = this.items;
    if (items.length === 0) return undefined;
    const first = items[0];
    const last = items.pop();
    if (items.length === 0) return first;
    items[0] = last;
    let index = 0;
    while (true) {
      const left = index * 2 + 1;
      const right = left + 1;
      let best = index;
      if (left < items.length && this.compare(items[left], items[best]) < 0) best = left;
      if (right < items.length && this.compare(items[right], items[best]) < 0) best = right;
      if (best === index) break;
      [items[index], items[best]] = [items[best], items[index]];
      index = best;
    }
    return first;
  }
}

Trace top-K by protecting the worst retained item

In Merge K Sorted Lists, store only the head of each nonempty list. After extracting one node, insert that node's successor. The frontier has at most K entries; storing every node up front discards the useful structure of the input.

1. For K = 3, insert 3, 2, and 1 into a min heap. The root is 1.
2. Insert 5. The heap now has four candidates, so pop its minimum, 1.
3. Insert 6 and pop 2. Insert 4 and pop 3.
4. The retained values are 4, 5, and 6. The root, 4, is the third largest.

Costs depend on frontier size

• peek is O(1). push and pop are O(log H), where H is the current heap size. Storage is O(H).
• The displayed constructor starts empty. Building by N repeated pushes is O(N log N) worst case; bottom-up heap construction is a separate O(N) algorithm.
• Keeping K candidates over N values takes O(N log(K + 1)) time and O(K) space. For K=1, the work is still linear.
• Merging N total list nodes with at most K active heads takes O(N log(K + 1)) time and O(K) heap space.
• For a static array that needs a full sorted result once, sorting can be simpler. A heap is not automatically the best choice for every top-K question.

Do not silently change the priority

• Re-sorting the entire candidate array after each insertion loses the heap's update bound.
• When sinking, compare both children and swap with the better one, not always the left child.
• Changing an object's priority after insertion can break the invariant. Reinsert a new immutable candidate or use a data structure supporting priority updates.
• A heap does not make a graph algorithm correct by itself. Define the score, relaxation rule, and stale-entry policy separately.
• For time-based frontend work, a heap orders events but does not implement timers, cancellation, or browser scheduling.

Mistakes and Counterexamples