Heap / Priority Queue
A heap is a complete binary tree that maintains the heap property: the parent is always smaller (min-heap) or larger (max-heap) than its children. This allows O(1) access to the minimum/maximum element and O(log n) insertion and removal. Heaps are the backbone of priority queues and are essential for problems requiring repeated access to the extreme element.
When to Use
- →You need repeated access to the minimum or maximum element
- →You need to merge K sorted lists or streams
- →You need to find the kth largest/smallest element efficiently
- →You need to schedule tasks by priority or maintain a running median
- →You need the top-K elements from a large dataset
Approach
JavaScript doesn't have a built-in heap, so you either implement one or use a sorted insertion approach for contest settings. A min-heap is an array where the parent at index i has children at 2i+1 and 2i+2. Insert by pushing to the end and bubbling up; remove the min by swapping root with the last element, popping, and bubbling down.
For kth largest problems, maintain a min-heap of size k. Every new element is compared with the heap's root (the smallest of the k largest). If it's bigger, remove the root and insert the new element. The root always holds the kth largest.
For running median, use two heaps: a max-heap for the lower half and a min-heap for the upper half. Balance their sizes so they differ by at most one. The median is the top of the larger heap (or the average of both tops if equal size).
Code Template
// MinHeap implementation
class MinHeap {
constructor() { this.data = []; }
size() { return this.data.length; }
peek() { return this.data[0]; }
push(val) {
this.data.push(val);
this._bubbleUp(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._bubbleDown(0);
}
return top;
}
_bubbleUp(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;
}
}
_bubbleDown(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[smallest], this.data[i]] = [this.data[i], this.data[smallest]];
i = smallest;
}
}
}