Min-Heap Template
JavaScript still has no built-in priority queue, so most real-world code rolls its own min-heap. This snippet covers a generic comparator-based heap with push and pop, the sift-up and sift-down internals that make both O(log n), and a heapify-from-array helper that builds a heap from an arbitrary input in O(n).
589 views
5
class MinHeap {
constructor(compare = (a, b) => a - b) {
this.data = [];
this.compare = compare;
}
get size() { return this.data.length; }
peek() { return this.data[0]; }
push(value) {
this.data.push(value);
this.#siftUp(this.data.length - 1);
}
pop() {
if (this.data.length === 0) return undefined;
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) {
while (i > 0) {
const parent = (i - 1) >>> 1;
if (this.compare(this.data[i], this.data[parent]) < 0) {
[this.data[i], this.data[parent]] = [this.data[parent], this.data[i]];
i = parent;
} else break;
}
}
#siftDown(i) {
const n = this.data.length;
while (true) {
const left = 2 * i + 1;
const right = 2 * i + 2;
let smallest = i;
if (left < n && this.compare(this.data[left], this.data[smallest]) < 0) smallest = left;
if (right < n && this.compare(this.data[right], this.data[smallest]) < 0) smallest = right;
if (smallest === i) break;
[this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
i = smallest;
}
}
}
const h = new MinHeap();
for (const x of [5, 3, 7, 1, 9, 2]) h.push(x);
const out = [];
while (h.size > 0) out.push(h.pop());
console.log(out); // [1, 2, 3, 5, 7, 9]The heap is stored as a plain array where parent(i) = (i - 1) / 2 and the children of i live at 2i + 1 and 2i + 2. push appends to the end and sifts up: bubble the new element toward the root while it is smaller than its parent. pop removes the root, moves the last element into its place, and sifts down: swap with the smaller child while invariant is broken. Both operations touch O(log n) levels. The comparator default (a, b) => a - b makes the structure a min-heap; pass (a, b) => b - a for a max-heap.
function heapSort(arr) {
const heap = new MinHeap();
for (const x of arr) heap.push(x);
const out = [];
while (heap.size > 0) out.push(heap.pop());
return out;
}
console.log(heapSort([4, 2, 7, 1, 9, 3])); // [1, 2, 3, 4, 7, 9]
console.log(heapSort([])); // []Pushing every element then popping every element gives a sorted result in O(n log n) total. This is heap sort, one of the canonical comparison-based sorts; it is in-place when the heap mutates the input array directly, but the version above is the simpler 'use the heap as a queue' variant. The advantage of heap sort over quicksort is its guaranteed O(n log n) worst case (no degenerate inputs), the disadvantage is its non-stable order. Use it as a baseline when you need predictable performance.
function topK(arr, k) {
const heap = new MinHeap();
for (const x of arr) {
heap.push(x);
if (heap.size > k) heap.pop();
}
const out = [];
while (heap.size > 0) out.push(heap.pop());
return out.reverse();
}
console.log(topK([3, 1, 5, 12, 2, 11], 3)); // [12, 11, 5]
console.log(topK([], 3)); // []Finding the K largest elements in O(n log k) is one of the headline applications of a min-heap. Maintain a heap of size K, push every element, and pop the smallest whenever the heap grows beyond K. The heap always contains the running 'top K so far', and the smallest of those is the threshold. Reversing at the end gives the largest first. This pattern beats sorting (O(n log n)) when K is much smaller than n, which is common in stream processing and 'top trending' queries.