Use min/max heaps for top-K problems, scheduling, and efficient repeated minimum extraction.
A heap is a complete binary tree satisfying the heap property: every node is ≤ (min-heap) or ≥ (max-heap) its children. It enables O(log n) insert and O(1) peek at the min/max. Most languages provide a priority queue built on a heap.
Insert O(log n) · Peek O(1) · Extract O(log n) · Build O(n)
O(n)
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Use this when you need the k largest elements from a stream or array
Maintain a min-heap of exactly size k. Push each new element; if the heap exceeds k, pop the minimum. After processing all elements, the heap contains the k largest. The top of the min-heap is the kth largest overall.
Problem Kth Largest Element in a Stream. Push each number; if size > k pop the smallest; the heap top is always the kth largest. class KthLargest { constructor(k, nums) { this.k = k; this.heap = new MinHeap(); for (const n of nums) this.add(n); } add(val) { this.heap.push(val); if (this.heap.size > this.k) this.heap.pop(); return this.heap.peek(); } }
// Top K elements — Kth Largest Element in an Array
// JavaScript lacks a built-in heap; we sort and take the top k here
function findKthLargest(nums, k) {
nums.sort((a, b) => b - a);
return nums[k - 1];
}
// For stream-based: maintain a sorted structure of size k
class KthLargestStream {
constructor(k, nums) { this.k = k; this.data = nums.sort((a,b) => a-b).slice(-k); }
add(val) {
let lo = 0, hi = this.data.length;
while (lo < hi) { const mid = (lo+hi)>>1; if (this.data[mid] < val) lo=mid+1; else hi=mid; }
this.data.splice(lo, 0, val);
if (this.data.length > this.k) this.data.shift();
return this.data[0];
}
}Use this when you need the k items with the highest frequency from a collection
First build a frequency map, then use a min-heap of size k keyed on frequency. Push each (frequency, element) pair; if the heap exceeds k, pop the least frequent.
Problem Top K Frequent Elements. Count frequencies with a map, then maintain a min-heap of size k on frequency values to find the k most frequent.
// K most frequent — Top K Frequent Elements
function topKFrequent(nums, k) {
const freq = new Map();
for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);
return [...freq.entries()]
.sort((a, b) => b[1] - a[1])
.slice(0, k)
.map(e => e[0]);
}Use this when K sorted lists must be merged into a single sorted output
Insert the head of each list into a min-heap keyed on node value. Repeatedly extract the minimum node, append it to the result, and push its next node (if any) into the heap. The heap always holds at most K nodes at once.
Problem Merge K Sorted Lists. Initialize the heap with the first node of each list; each extraction produces the next merged node.
// Merge K sorted lists — simulate with sorted array (no built-in heap)
function mergeKLists(lists) {
const dummy = new ListNode(0);
let curr = dummy;
const nodes = [];
for (const head of lists) { let n = head; while (n) { nodes.push(n.val); n = n.next; } }
nodes.sort((a, b) => a - b);
for (const v of nodes) { curr.next = new ListNode(v); curr = curr.next; }
return dummy.next;
}Use this when you need the running median as numbers are inserted one at a time
Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half. After each insertion, rebalance so the sizes differ by at most one. The median is either the top of the larger heap or the average of both tops.
Problem Find Median from Data Stream. Lower max-heap gets new element first, then the root is moved to the upper min-heap; rebalance sizes if needed. class MedianFinder { addNum(num) { this.lower.push(num); this.upper.push(this.lower.pop()); if (this.upper.size > this.lower.size) this.lower.push(this.upper.pop()); } findMedian() { return this.lower.size > this.upper.size ? this.lower.peek() : (this.lower.peek() + this.upper.peek()) / 2; } }
// Running median — two heaps (simulate with sorted array)
class MedianFinder {
constructor() { this.data = []; }
addNum(num) {
let lo = 0, hi = this.data.length;
while (lo < hi) { const mid=(lo+hi)>>1; if(this.data[mid]<num) lo=mid+1; else hi=mid; }
this.data.splice(lo, 0, num);
}
findMedian() {
const n = this.data.length;
return n % 2 === 0
? (this.data[n/2-1] + this.data[n/2]) / 2
: this.data[Math.floor(n/2)];
}
}Use this when you need the K points nearest to the origin from a list of points, using Euclidean distance squared to avoid floating point
Maintain a max-heap of size k keyed on distance; pop the farthest point when the heap exceeds k. What remains are the k closest.
Problem K Closest Points to Origin. Push (dist, point); when size > k pop the max-dist entry; the heap holds the k closest.
// K closest points to origin — sort by distance squared
function kClosest(points, k) {
return points
.sort((a, b) => (a[0]*a[0]+a[1]*a[1]) - (b[0]*b[0]+b[1]*b[1]))
.slice(0, k);
}Use this when tasks or characters must be scheduled such that the most frequent items are spread out
Use a max-heap to always pick the item with the highest remaining count, and a cooldown queue to hold items that are in their cooldown period. This greedy-with-heap approach produces the optimal arrangement.
Problem Reorganize String. Always place the most frequent unused character; if the previous character is now off cooldown, return it to the heap.
// Task scheduling — Reorganize String (greedy even-index fill)
function reorganizeString(s) {
const freq = new Array(26).fill(0);
for (const c of s) freq[c.charCodeAt(0) - 97]++;
const maxFreq = Math.max(...freq);
if (maxFreq > Math.ceil(s.length / 2)) return "";
const sorted = freq.map((f, i) => [f, i]).sort((a, b) => b[0] - a[0]);
const res = new Array(s.length);
let idx = 0;
for (const [f, c] of sorted) {
for (let i = 0; i < f; i++) {
if (idx >= s.length) idx = 1;
res[idx] = String.fromCharCode(c + 97);
idx += 2;
}
}
return res.join("");
}