Heap

Build a binary heap — the data structure that backs every priority queue you've ever used. You're given a stream of values and you need to repeatedly pull out the smallest one cheaply, no matter how many more arrive in the meantime. A sorted array gives you O(1) reads but O(n) writes; an unsorted array gives you O(1) writes but O(n) reads. A heap gives you O(log n) on both, using nothing more than a plain array with some index arithmetic. See MDN's note on priority queues for the broader family. You'll ship a Heap class with push, pop, peek, a size getter, and a static Heap.heapify that builds a heap from an existing array in linear time.

Signature

class Heap {
  constructor(compare = (a, b) => a - b)      // default min-heap
  push(value): void                            // O(log n)
  pop(): T | undefined                         // remove + return root; undefined when empty
  peek(): T | undefined                        // read root without removing; O(1)
  get size(): number                           // current element count

  static heapify(array, compare?): Heap        // O(n) build from an existing array
}

The comparator follows the same convention as Array.prototype.sort: it returns a negative number if a should come out before b, positive if b should come out first, and 0 if they're equal. The default (a, b) => a - b makes a min-heap (smallest comes out first).

Examples

Basic min-heap usage — push in any order, pop in sorted order:

const h = new Heap();
h.push(5); h.push(1); h.push(3); h.push(8); h.push(2);
h.size;     // 5
h.peek();   // 1  (smallest, without removing)
h.pop();    // 1
h.pop();    // 2
h.pop();    // 3
h.size;     // 2

Empty heap — pop and peek both return undefined, never throw:

const h = new Heap();
h.peek();   // undefined
h.pop();    // undefined
h.size;     // 0

Max-heap via a flipped comparator:

const max = new Heap((a, b) => b - a);
max.push(1); max.push(9); max.push(4);
max.pop();  // 9
max.pop();  // 4
max.pop();  // 1

Object comparator — extract any field you want to prioritise on:

const tasks = new Heap((a, b) => a.priority - b.priority);
tasks.push({ id: 'a', priority: 3 });
tasks.push({ id: 'b', priority: 1 });
tasks.push({ id: 'c', priority: 2 });
tasks.pop();  // { id: 'b', priority: 1 }

Static heapify — build a heap from an existing array in O(n), not O(n log n):

const h = Heap.heapify([5, 1, 8, 3, 2, 9, 4]);
h.pop();  // 1
h.pop();  // 2
h.pop();  // 3

Notes

• Default is a min-heap — the smallest value comes out first. This matches Python's heapq and is the most common convention; for a max-heap, pass (a, b) => b - a.
• pop and peek on an empty heap return undefined — they do not throw. This matches Array.prototype.pop's behaviour and lets callers loop while (h.size) ... without special-casing.
• size is a getter, not a method — read it as h.size, not h.size(). Same shape as Array.prototype.length.
• Duplicates are allowed — heaps make no claim about the order of equal-keyed items (heaps are not stable). If your comparator returns 0 for two values, either may come out first.
• Heap.heapify returns a new heap and does not mutate the input array — copy in, heap out. The interesting bit is that the build is O(n), not O(n log n); see the solution for why.
• Out of scope — delete(value), decreaseKey(index, value), iteration order via for..of. Just the methods above.