Introduction
A Min Heap is a special type of binary tree where the smallest element is always at the root. It’s a fundamental data structure used in various algorithms like Dijkstra’s shortest path, Prim’s minimum spanning tree, and in priority queues where you always need to fetch the smallest (or highest priority) element efficiently.
In this article, you’ll understand the underlying logic, explore its core operations, and see how to visualize and test it. This guide is written in simple, natural language and optimized for SEO keywords such as min heap JavaScript, JavaScript priority queue, heapify in JS, and build a heap from array.
What is a Min Heap?
A Min Heap is a complete binary tree that satisfies the heap property:
Every parent node is smaller than or equal to its children.
Because the heap is complete, it can be stored efficiently in an array. The index relationships are:
Parent index: parent(i) = Math.floor((i - 1) / 2)
Left child: left(i) = 2 * i + 1
Right child: right(i) = 2 * i + 2
This array-based representation saves memory and simplifies operations.
Time Complexity Overview
| Operation | Description | Time Complexity |
|---|
| peek() | Get the smallest element (root) | O(1) |
| insert(value) | Add an element and restore heap order | O(log n) |
| extractMin() | Remove root and restore heap order | O(log n) |
| heapify(array) | Build heap from an array | O(n) |
Step-by-Step Implementation in JavaScript
Below is a complete MinHeap class in JavaScript, written for clarity and efficiency.
MinHeap Implementation:
class MinHeap {
constructor(comparator = (a, b) => a - b, items = []) {
this._cmp = comparator;
this.heap = Array.isArray(items) ? items.slice() : [];
if (this.heap.length > 0) this._heapify();
}
size() { return this.heap.length; }
isEmpty() { return this.size() === 0; }
peek() { return this.heap[0] ?? null; }
insert(value) {
this.heap.push(value);
this._bubbleUp(this.heap.length - 1);
}
extractMin() {
if (this.heap.length === 0) return null;
const min = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this._siftDown(0);
}
return min;
}
_parent(i) { return Math.floor((i - 1) / 2); }
_left(i) { return 2 * i + 1; }
_right(i) { return 2 * i + 2; }
_swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; }
_bubbleUp(i) {
while (i > 0) {
const p = this._parent(i);
if (this._cmp(this.heap[i], this.heap[p]) < 0) {
this._swap(i, p);
i = p;
} else break;
}
}
_siftDown(i) {
const n = this.heap.length;
while (true) {
const l = this._left(i);
const r = this._right(i);
let smallest = i;
if (l < n && this._cmp(this.heap[l], this.heap[smallest]) < 0) smallest = l;
if (r < n && this._cmp(this.heap[r], this.heap[smallest]) < 0) smallest = r;
if (smallest !== i) {
this._swap(i, smallest);
i = smallest;
} else break;
}
}
_heapify() {
const start = Math.floor(this.heap.length / 2) - 1;
for (let i = start; i >= 0; i--) this._siftDown(i);
}
toArray() { return this.heap.slice(); }
toSortedArray() {
const copy = new MinHeap(this._cmp, this.heap.slice());
const result = [];
while (!copy.isEmpty()) result.push(copy.extractMin());
return result;
}
}
Example Usage
const heap = new MinHeap();
heap.insert(5);
heap.insert(3);
heap.insert(8);
heap.insert(1);
console.log(heap.peek()); // 1
console.log(heap.extractMin()); // 1
console.log(heap.toArray()); // [3,5,8]
Custom Comparator Example
To use a heap with objects (e.g., a priority queue):
const pq = new MinHeap((a, b) => a.priority - b.priority);
pq.insert({ task: 'Fix bugs', priority: 3 });
pq.insert({ task: 'Write docs', priority: 5 });
pq.insert({ task: 'Deploy app', priority: 1 });
console.log(pq.extractMin());
// Output: { task: 'Deploy app', priority: 1 }
Visualization of Bubble-Up and Sift-Down
Bubble-Up Example (Insert 1)
Start: [5, 6, 7, 10]
Insert 1 → [5, 6, 7, 10, 1]
Swap(1, 6) → [5, 1, 7, 10, 6]
Swap(5, 1) → [1, 5, 7, 10, 6]
Result: [1, 5, 7, 10, 6]
Sift-Down Example (ExtractMin)
Start: [1, 5, 7, 10, 6]
Remove root 1 → [6, 5, 7, 10]
Swap(6, 5) → [5, 6, 7, 10]
Result: [5, 6, 7, 10]
Testing the Min Heap with Jest
const MinHeap = require('./MinHeap');
describe('MinHeap', () => {
test('insert and extractMin', () => {
const heap = new MinHeap();
[5, 1, 3, 2, 4].forEach(v => heap.insert(v));
const result = [];
while (!heap.isEmpty()) result.push(heap.extractMin());
expect(result).toEqual([1, 2, 3, 4, 5]);
});
test('custom comparator works', () => {
const heap = new MinHeap((a, b) => a.priority - b.priority);
heap.insert({ task: 'A', priority: 3 });
heap.insert({ task: 'B', priority: 1 });
expect(heap.extractMin().priority).toBe(1);
});
});
Run with:
npm install --save-dev jest
npm test
Visualization in Browser
You can also visualize heap operations interactively with a simple HTML + JS visualizer. Use this snippet in a browser:
<!DOCTYPE html>
<html>
<head>
<style>
body { font-family: Arial; }
.heap { display:flex; gap:8px; flex-wrap:wrap; margin-top:10px; }
.node { width:40px; height:40px; display:flex; align-items:center; justify-content:center; border-radius:6px; background:#007acc; color:white; }
</style>
</head>
<body>
<h3>Min Heap Visualizer</h3>
<button onclick="insertRandom()">Insert Random</button>
<button onclick="extract()">Extract Min</button>
<div class="heap" id="heap"></div>
<script>
class HeapVis {
constructor(){ this.heap=[]; }
parent(i){ return Math.floor((i-1)/2); }
left(i){ return 2*i+1; }
right(i){ return 2*i+2; }
swap(i,j){ [this.heap[i],this.heap[j]]=[this.heap[j],this.heap[i]]; }
insert(v){ this.heap.push(v); this.bubble(this.heap.length-1); this.render(); }
extract(){ if(!this.heap.length)return; const min=this.heap[0]; const last=this.heap.pop(); if(this.heap.length){this.heap[0]=last; this.sift(0);} this.render(); alert('Extracted '+min); }
bubble(i){ while(i>0){ const p=this.parent(i); if(this.heap[i]<this.heap[p]){this.swap(i,p); i=p;} else break;} }
sift(i){ const n=this.heap.length; while(true){ const l=this.left(i),r=this.right(i); let s=i; if(l<n&&this.heap[l]<this.heap[s])s=l; if(r<n&&this.heap[r]<this.heap[s])s=r; if(s!==i){this.swap(i,s); i=s;} else break;} }
render(){ const div=document.getElementById('heap'); div.innerHTML=''; this.heap.forEach(v=>{const n=document.createElement('div');n.className='node';n.textContent=v;div.appendChild(n);}); }
}
const hv=new HeapVis();
function insertRandom(){ hv.insert(Math.floor(Math.random()*100)); }
function extract(){ hv.extract(); }
</script>
</body>
</html>
Summary
Implementing a Min Heap in JavaScript helps you understand one of the most powerful data structures for efficient sorting, priority queues, and algorithm optimization. You learned how to:
Build a heap from scratch using an array.
Implement insert, extractMin, and peek methods.
Use a custom comparator for complex data.
Visualize heap operations and test them with Jest.
By mastering heaps, you’ll improve your understanding of algorithmic efficiency and data manipulation in JavaScript — a key skill for advanced front-end and back-end development.