A heap is a complete binary tree that satisfies the heap property:
Heaps are typically stored as arrays for efficiency:
// Array representation:
// Parent of i: Math.floor((i - 1) / 2)
// Left child of i: 2 * i + 1
// Right child of i: 2 * i + 2
// Min-Heap example:
// 1
// / \
// 3 5
// / \
// 7 9
// Array: [1, 3, 5, 7, 9]
Key operations: insert O(log n), extract min/max O(log n), peek O(1).
Min-Heap: The smallest element is always at the root. Every parent is ≤ its children.
Max-Heap: The largest element is always at the root. Every parent is ≥ its children.
// Min-Heap: Max-Heap:
// 1 9
// / \ / \
// 3 5 7 5
// / \ / \
// 7 9 1 3
// Use min-heap when you need quick access to the smallest element.
// Use max-heap when you need quick access to the largest element.
Insert: Add element at the end, then bubble up (swap with parent while heap property is violated).
Extract: Remove root, move last element to root, then bubble down (swap with smaller/larger child).
class MinHeap {
constructor() { this.heap = []; }
insert(val) {
this.heap.push(val);
this._bubbleUp(this.heap.length - 1);
}
extractMin() {
const min = this.heap[0];
const last = this.heap.pop();
if (this.heap.length) { this.heap[0] = last; this._bubbleDown(0); }
return min;
}
_bubbleUp(i) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.heap[parent] <= this.heap[i]) break;
[this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
i = parent;
}
}
_bubbleDown(i) {
const n = this.heap.length;
while (2 * i + 1 < n) {
let smallest = 2 * i + 1;
if (smallest + 1 < n && this.heap[smallest + 1] < this.heap[smallest]) smallest++;
if (this.heap[i] <= this.heap[smallest]) break;
[this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
i = smallest;
}
}
}
Heapify converts an unordered array into a valid heap. It works by calling bubble down on all non-leaf nodes from bottom to top.
function heapify(arr) {
const n = arr.length;
// Start from last non-leaf node
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
bubbleDown(arr, i, n);
}
return arr;
}
function bubbleDown(arr, i, n) {
while (2 * i + 1 < n) {
let smallest = 2 * i + 1;
if (smallest + 1 < n && arr[smallest + 1] < arr[smallest]) smallest++;
if (arr[i] <= arr[smallest]) break;
[arr[i], arr[smallest]] = [arr[smallest], arr[i]];
i = smallest;
}
}
// heapify([9, 5, 7, 1, 3]) => [1, 3, 7, 9, 5]
Time: O(n) — not O(n log n)! Most nodes are near the bottom and require few swaps.
Heap Sort builds a max-heap, then repeatedly extracts the maximum and places it at the end.
function heapSort(arr) {
const n = arr.length;
// Build max-heap
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
maxHeapify(arr, i, n);
}
// Extract elements one by one
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]]; // move max to end
maxHeapify(arr, 0, i); // re-heapify reduced heap
}
return arr;
}
function maxHeapify(arr, i, n) {
while (2 * i + 1 < n) {
let largest = 2 * i + 1;
if (largest + 1 < n && arr[largest + 1] > arr[largest]) largest++;
if (arr[i] >= arr[largest]) break;
[arr[i], arr[largest]] = [arr[largest], arr[i]];
i = largest;
}
}
Time: O(n log n) | Space: O(1) in-place. Not stable.
Use a min-heap of size k. The root of this heap will be the kth largest element.
function kthLargest(nums, k) {
const minHeap = new MinHeap();
for (const num of nums) {
minHeap.insert(num);
if (minHeap.size() > k) {
minHeap.extractMin(); // remove smallest
}
}
return minHeap.peek(); // kth largest
}
// kthLargest([3,2,1,5,6,4], 2) => 5
// kthLargest([3,2,3,1,2,4,5,5,6], 4) => 4
Time: O(n log k) | Space: O(k). Better than sorting when k ≪ n.
Insert the head of each list into a min-heap. Extract the minimum, add it to the result, and insert the next element from that list.
function mergeKSorted(lists) {
const minHeap = new MinHeap(); // stores {val, listIdx, elemIdx}
// Initialize with first element of each list
for (let i = 0; i < lists.length; i++) {
if (lists[i].length) {
minHeap.insert({ val: lists[i][0], listIdx: i, elemIdx: 0 });
}
}
const result = [];
while (minHeap.size() > 0) {
const { val, listIdx, elemIdx } = minHeap.extractMin();
result.push(val);
if (elemIdx + 1 < lists[listIdx].length) {
minHeap.insert({
val: lists[listIdx][elemIdx + 1],
listIdx,
elemIdx: elemIdx + 1
});
}
}
return result;
}
Time: O(N log k) where N = total elements, k = number of lists | Space: O(k)
A priority queue is an abstract data type typically implemented using a heap for efficient operations.
class PriorityQueue {
constructor(compareFn = (a, b) => a - b) {
this.heap = [];
this.compare = compareFn;
}
enqueue(val) {
this.heap.push(val);
let i = this.heap.length - 1;
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.compare(this.heap[i], this.heap[parent]) >= 0) break;
[this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
i = parent;
}
}
dequeue() {
const top = this.heap[0];
const last = this.heap.pop();
if (this.heap.length) { this.heap[0] = last; this._siftDown(0); }
return top;
}
_siftDown(i) { /* same as bubbleDown */ }
peek() { return this.heap[0]; }
size() { return this.heap.length; }
}
Enqueue: O(log n) | Dequeue: O(log n) | Peek: O(1)
Count frequencies with a hash map, then use a min-heap of size K to track the top K frequent elements.
function topKFrequent(nums, k) {
// Step 1: Count frequencies
const freq = new Map();
for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
// Step 2: Use bucket sort (alternative to heap)
const buckets = new Array(nums.length + 1).fill(null).map(() => []);
for (const [num, count] of freq) {
buckets[count].push(num);
}
// Step 3: Collect top K from highest frequency buckets
const result = [];
for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
result.push(...buckets[i]);
}
return result.slice(0, k);
}
// topKFrequent([1,1,1,2,2,3], 2) => [1, 2]
Time: O(n) with bucket sort | Space: O(n)
Use two heaps: a max-heap for the lower half and a min-heap for the upper half. The median is derived from the tops of the heaps.
class MedianFinder {
constructor() {
this.maxHeap = new MaxHeap(); // lower half
this.minHeap = new MinHeap(); // upper half
}
addNum(num) {
this.maxHeap.insert(num);
// Ensure max-heap's top <= min-heap's top
this.minHeap.insert(this.maxHeap.extractMax());
// Balance sizes (maxHeap can have at most 1 more)
if (this.minHeap.size() > this.maxHeap.size()) {
this.maxHeap.insert(this.minHeap.extractMin());
}
}
findMedian() {
if (this.maxHeap.size() > this.minHeap.size()) {
return this.maxHeap.peek();
}
return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
}
}
// addNum(1), addNum(2) => median = 1.5
// addNum(3) => median = 2
addNum: O(log n) | findMedian: O(1)
Maintain a min-heap of size k. For each element, add it and if heap exceeds k, remove the minimum. The heap's root is the kth largest.
// Using a simulated min-heap via sorted array (JavaScript has no native heap)
function findKthLargest(nums, k) {
// Simple approach: sort descending
nums.sort((a, b) => b - a);
return nums[k - 1];
}
// With a real MinHeap:
function findKthLargestHeap(nums, k) {
const heap = new MinHeap();
for (const num of nums) {
heap.insert(num);
if (heap.size() > k) heap.extractMin(); // keep only k largest
}
return heap.peek(); // min of the k largest = kth largest
}
// Input: nums=[3,2,1,5,6,4], k=2 => Output: 5
// Input: nums=[3,2,3,1,2,4,5,5,6], k=4 => Output: 4
Time: O(n log k) | Space: O(k)
Push the first element of each array into a min-heap along with its array index and element index. Pop the minimum, add to result, then push the next element from the same array.
function mergeKSortedArrays(arrays) {
// Min-heap stores [value, arrayIndex, elementIndex]
const heap = [];
const result = [];
// Initialize: push first element of each array
for (let i = 0; i < arrays.length; i++) {
if (arrays[i].length) heap.push([arrays[i][0], i, 0]);
}
heap.sort((a, b) => a[0] - b[0]); // initial sort
while (heap.length) {
const [val, ai, ei] = heap.shift(); // extract min
result.push(val);
if (ei + 1 < arrays[ai].length) {
// Insert next element, then re-sort (heap operation)
heap.push([arrays[ai][ei + 1], ai, ei + 1]);
heap.sort((a, b) => a[0] - b[0]);
}
}
return result;
}
// Input: [[1,4,7],[2,5,8],[3,6,9]] => Output: [1,2,3,4,5,6,7,8,9]
// Input: [[1,2],[3,4],[5]] => Output: [1,2,3,4,5]
Time: O(n log k) with proper heap | Space: O(k) for the heap
Use a priority queue (min-heap) keyed by distance. Start from source, greedily explore the closest unvisited node and relax edges.
function dijkstra(graph, src) {
// graph: adjacency list { node: [[neighbor, weight], ...] }
const dist = {};
for (const node in graph) dist[node] = Infinity;
dist[src] = 0;
// Min-heap: [distance, node]
const pq = [[0, src]]; // simulate with sorted array
while (pq.length) {
pq.sort((a, b) => a[0] - b[0]);
const [d, u] = pq.shift();
if (d > dist[u]) continue; // stale entry
for (const [v, weight] of (graph[u] || [])) {
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push([dist[v], v]);
}
}
}
return dist;
}
// Graph: A->B(1), A->C(4), B->C(2), B->D(5), C->D(1)
// dijkstra(graph, "A") => {A:0, B:1, C:3, D:4}
Time: O((V + E) log V) | Space: O(V)
Build a frequency map, then use a min-heap of size k. Push each (freq, element) pair; when size exceeds k, extract the minimum. Result is the top k.
function topKFrequentHeap(nums, k) {
const freq = new Map();
for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
// Sort by frequency, take top k
return [...freq.entries()]
.sort((a, b) => b[1] - a[1])
.slice(0, k)
.map(([num]) => num);
}
// Input: nums=[1,1,1,2,2,3], k=2 => Output: [1,2]
// Input: nums=[4,4,4,3,3,2,1], k=3 => Output: [4,3,2]
Time: O(n log k) with a proper heap, O(n log n) with sort | Space: O(n)
Greedy using a max-heap by frequency. Always pick the most frequent character that isn't the same as the last placed character.
function reorganizeString(s) {
const freq = {};
for (const c of s) freq[c] = (freq[c] || 0) + 1;
// Sort by frequency descending (simulate max-heap)
const entries = Object.entries(freq).sort((a, b) => b[1] - a[1]);
const result = [];
while (entries[0] && entries[0][1] > 0) {
// Place most frequent
const [c1, f1] = entries[0];
if (result[result.length-1] === c1) {
if (!entries[1] || entries[1][1] === 0) return ''; // impossible
const [c2, f2] = entries[1];
result.push(c2);
entries[1] = [c2, f2 - 1];
} else {
result.push(c1);
entries[0] = [c1, f1 - 1];
}
entries.sort((a, b) => b[1] - a[1]); // re-sort after update
}
return result.join('');
}
// Input: "aab" => Output: "aba"
// Input: "aaab" => Output: "" (impossible)
// Input: "aabb" => Output: "abab"
Time: O(n log k) | Space: O(k) unique chars
Use a max-heap of size k. For each point, compute squared distance; if it's smaller than the heap's max, replace it. Final heap contains the k closest.
function kClosest(points, k) {
// Sort by squared Euclidean distance
points.sort((a, b) => (a[0]**2 + a[1]**2) - (b[0]**2 + b[1]**2));
return points.slice(0, k);
}
// With proper max-heap of size k (O(n log k)):
// Keep heap of k smallest; each new point evicts the largest if smaller
// Input: [[1,3],[-2,2]], k=1 => Output: [[-2,2]] (dist=8 vs dist=10)
// Input: [[3,3],[5,-1],[-2,4]], k=2 => Output: [[3,3],[-2,4]]
Time: O(n log k) heap / O(n log n) sort | Space: O(k)
Sort jobs by profit descending. Use a min-heap of size = deadline. Greedily add profitable jobs, evicting the least profitable if the heap is full.
function jobScheduling(jobs) {
// jobs: [[startTime, endTime, profit]]
// Sort by end time
jobs.sort((a, b) => a[1] - b[1]);
const dp = [[0, 0]]; // [endTime, maxProfit]
for (const [start, end, profit] of jobs) {
// Find last job that ends before start (binary search)
let lo = 0, hi = dp.length - 1;
while (lo < hi) {
const mid = Math.ceil((lo + hi) / 2);
if (dp[mid][0] <= start) lo = mid; else hi = mid - 1;
}
const newProfit = dp[lo][1] + profit;
if (newProfit > dp[dp.length-1][1]) {
dp.push([end, newProfit]);
}
}
return dp[dp.length-1][1];
}
// jobs=[[1,2,50],[3,5,20],[6,19,100],[2,100,200]] => Output: 250
Time: O(n log n) | Space: O(n)
Build a max-heap in-place (heapify), then repeatedly extract the max to the end of the array. The array becomes sorted.
function heapSort(arr) {
const n = arr.length;
// Build max-heap (heapify from last non-leaf to root)
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(arr, n, i);
// Extract elements one by one
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]]; // move max to end
heapify(arr, i, 0); // restore heap for remaining elements
}
return arr;
}
function heapify(arr, n, i) {
let largest = i, l = 2*i+1, r = 2*i+2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest);
}
}
// Input: [12,11,13,5,6,7] => Output: [5,6,7,11,12,13]
// Input: [4,10,3,5,1] => Output: [1,3,4,5,10]
Time: O(n log n) | Space: O(1) in-place
Push (value, row, col) for the first element of each row into a min-heap. Pop the min k times; each time push the next element in the same row.
function kthSmallestMatrix(matrix, k) {
const n = matrix.length;
// Min-heap: [value, row, col]
const heap = matrix.map((row, r) => [row[0], r, 0]);
heap.sort((a, b) => a[0] - b[0]);
let result = 0;
for (let i = 0; i < k; i++) {
heap.sort((a, b) => a[0] - b[0]);
const [val, r, c] = heap.shift();
result = val;
if (c + 1 < n) heap.push([matrix[r][c + 1], r, c + 1]);
}
return result;
}
// Matrix: [[1,5,9],[10,11,13],[12,13,15]], k=8 => Output: 13
// Matrix: [[-5]], k=1 => Output: -5
Time: O(k log n) | Space: O(n)
A priority queue dequeues the highest (or lowest) priority element first, unlike a regular queue that dequeues in insertion order (FIFO).
// JavaScript simulation of a Min Priority Queue
class PriorityQueue {
constructor() { this.heap = []; }
push(val, priority) {
this.heap.push({ val, priority });
this.heap.sort((a, b) => a.priority - b.priority);
}
pop() { return this.heap.shift(); }
peek() { return this.heap[0]; }
size() { return this.heap.length; }
}
const pq = new PriorityQueue();
pq.push("low", 5); pq.push("high", 1); pq.push("medium", 3);
pq.pop().val // => "high" (priority 1 = highest)
Time: O(log n) push/pop with binary heap | Space: O(n)
Always connect the two shortest ropes. Use a min-heap: extract two minimums, compute their sum (cost), insert the sum back.
function connectRopes(ropes) {
// Simulate min-heap with sort
ropes.sort((a, b) => a - b);
let totalCost = 0;
while (ropes.length > 1) {
ropes.sort((a, b) => a - b); // ensure sorted after each insert
const first = ropes.shift();
const second = ropes.shift();
const combined = first + second;
totalCost += combined;
ropes.push(combined);
}
return totalCost;
}
// Input: [4, 3, 2, 6] => Output: 29
// (2+3=5, cost=5), (4+5=9, cost=14), (6+9=15, cost=29)
// Input: [1, 2, 3, 4, 5] => Output: 33
Time: O(n log n) | Space: O(1) (modifies input array)
Use two Maps: freq (remaining counts) and end (open subsequences that can be extended). Greedily extend existing sequences before creating new ones.
function isPossible(nums) {
const freq = new Map(), end = new Map();
for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
for (const n of nums) {
if (!freq.get(n)) continue; // already used
if (end.get(n) > 0) {
// Extend existing sequence ending at n-1
end.set(n, (end.get(n) || 0) - 1);
end.set(n + 1, (end.get(n + 1) || 0) + 1);
} else if (freq.get(n + 1) > 0 && freq.get(n + 2) > 0) {
// Start new sequence n, n+1, n+2
freq.set(n + 1, freq.get(n + 1) - 1);
freq.set(n + 2, freq.get(n + 2) - 1);
end.set(n + 3, (end.get(n + 3) || 0) + 1);
} else return false;
freq.set(n, freq.get(n) - 1);
}
return true;
}
// Input: [1,2,3,3,4,5] => Output: true ([1,2,3] and [3,4,5])
// Input: [1,2,3,3,4,4,5,5] => Output: true
// Input: [1,2,3,4,4,5] => Output: false
Time: O(n) | Space: O(n)