Revision 1·28 Sept
Heap Introduction
DifficultyMedium
PatternTwo Heap
TrackDSA
tl;dr
Here we'll learn about heap
full write-up
Here we'll learn about heap
What Is a Heap?
A heap is a complete binary tree.
A complete binary tree is a tree where:
- Every level is fully filled, except maybe the last level.
- The last level is filled from left to right.
Types of Heaps
There are two types of heaps:
- Min Heap: The parent node is always less than or equal to its child nodes.
- Max Heap: The parent node is always more than or equal to its child nodes.
How to Create a Max Heap
We build a heap using an array, not a linked list. Using a linked list would make swapping nodes more complex.
Here is how it works:
- We add elements to the array one by one.
- After each insertion, we check if the new element is in the correct position.
- To check this, we compare the new element with its parent. The new element should always be less than or equal to its parent.
Finding Parent and Child Nodes
We can find related nodes using simple math on their index (i):
- Parent node index:
(i - 1) / 2 - Left child index:
2 * i + 1 - Right child index:
2 * i + 2
Bubble Up and Bubble Down
There are two ways to fix a heap's order:
- Bubble up: Used when we insert a new element. We compare the new element with its parent. If it is bigger than the parent, we swap them. We repeat this until the element is in the correct spot.
- Bubble down: Used when we turn an existing array into a heap, or after we remove the root node. We compare a node with its left and right child. Whichever child is bigger, we swap it with the parent. We repeat this until the node is in the correct spot.
Removing the Root Node
If we delete the root node from a max heap:
- We move the last leaf node to the root position.
- We use bubble down to move it to its correct spot.
Code: Max Heap in JavaScript
class MaxHeap {
constructor() {
this.heap = [];
}
size() {
return this.heap.length;
}
isEmpty() {
return this.heap.length === 0;
}
peek() {
if (this.isEmpty()) return null;
return this.heap[0];
}
// --- Helper index methods ---
getParentIndex(i) {
return Math.floor((i - 1) / 2);
}
getLeftChildIndex(i) {
return 2 * i + 1;
}
getRightChildIndex(i) {
return 2 * i + 2;
}
swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
// --- Insert a value ---
insert(value) {
this.heap.push(value);
this.bubbleUp(this.heap.length - 1);
}
bubbleUp(index) {
while (index > 0) {
const parentIndex = this.getParentIndex(index);
if (this.heap[parentIndex] >= this.heap[index]) break;
this.swap(parentIndex, index);
index = parentIndex;
}
}
// --- Remove and return the max value ---
extractMax() {
if (this.isEmpty()) return null;
const max = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this.bubbleDown(0);
}
return max;
}
bubbleDown(index) {
const n = this.heap.length;
while (true) {
const left = this.getLeftChildIndex(index);
const right = this.getRightChildIndex(index);
let largest = index;
if (left < n && this.heap[left] > this.heap[largest]) {
largest = left;
}
if (right < n && this.heap[right] > this.heap[largest]) {
largest = right;
}
if (largest === index) break;
this.swap(index, largest);
index = largest;
}
}
// --- Build a heap from an existing array ---
buildHeap(arr) {
this.heap = [...arr];
for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
this.bubbleDown(i);
}
}
toArray() {
return [...this.heap];
}
}
// --- Example usage ---
const heap = new MaxHeap();
[5, 3, 8, 1, 9, 2].forEach(val => heap.insert(val));
console.log("Heap array:", heap.toArray());
console.log("Peek max:", heap.peek()); // 9
console.log("Extract max:", heap.extractMax()); // 9
console.log("Extract max:", heap.extractMax()); // 8
console.log("Heap after extracts:", heap.toArray());
Code: Min Heap in JavaScript
class MinHeap {
constructor() {
this.heap = [];
}
size() {
return this.heap.length;
}
isEmpty() {
return this.heap.length === 0;
}
peek() {
if (this.isEmpty()) return null;
return this.heap[0];
}
getParentIndex(i) {
return Math.floor((i - 1) / 2);
}
getLeftChildIndex(i) {
return 2 * i + 1;
}
getRightChildIndex(i) {
return 2 * i + 2;
}
swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
insert(value) {
this.heap.push(value);
this.bubbleUp(this.heap.length - 1);
}
bubbleUp(index) {
while (index > 0) {
const parentIndex = this.getParentIndex(index);
if (this.heap[parentIndex] <= this.heap[index]) break;
this.swap(parentIndex, index);
index = parentIndex;
}
}
extractMin() {
if (this.isEmpty()) return null;
const min = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this.bubbleDown(0);
}
return min;
}
bubbleDown(index) {
const n = this.heap.length;
while (true) {
const left = this.getLeftChildIndex(index);
const right = this.getRightChildIndex(index);
let smallest = index;
if (left < n && this.heap[left] < this.heap[smallest]) {
smallest = left;
}
if (right < n && this.heap[right] < this.heap[smallest]) {
smallest = right;
}
if (smallest === index) break;
this.swap(index, smallest);
index = smallest;
}
}
buildHeap(arr) {
this.heap = [...arr];
for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
this.bubbleDown(i);
}
}
toArray() {
return [...this.heap];
}
}
// --- Example usage ---
const heap = new MinHeap();
[5, 3, 8, 1, 9, 2].forEach(val => heap.insert(val));
console.log("Heap array:", heap.toArray());
console.log("Peek min:", heap.peek()); // 1
console.log("Extract min:", heap.extractMin()); // 1
console.log("Extract min:", heap.extractMin()); // 2
console.log("Heap after extracts:", heap.toArray());
Universal heap
class NewHeap {
constructor(data = [], compare = (a, b) => a - b) {
this.data = [...data];
this.compare = compare;
// Convert the entire array into a heap.
this.heapify();
}
// Returns the number of elements in the heap.
size() {
return this.data.length;
}
// Returns true if the heap is empty.
isEmpty() {
return this.data.length === 0;
}
// Returns the root element without removing it.
peek() {
return this.isEmpty() ? null : this.data[0];
}
// Adds a new element to the heap.
offer(value) {
this.data.push(value);
this.percolateUp(this.size() - 1);
}
// Removes and returns the root element.
poll() {
if (this.isEmpty()) {
return null;
}
const root = this.data[0];
const last = this.data.pop();
if (!this.isEmpty()) {
this.data[0] = last;
this.percolateDown(0);
}
return root;
}
// Removes all elements from the heap.
clear() {
this.data.length = 0;
}
// Converts the entire array into a heap.
// Time complexity: O(n)
heapify() {
const firstParent = Math.floor(this.size() / 2) - 1;
for (let i = firstParent; i >= 0; i--) {
this.percolateDown(i);
}
}
// Restores the heap property by moving an element upward.
percolateUp(index) {
while (index > 0) {
const parent = Math.floor((index - 1) / 2);
// If the parent is already correctly ordered, stop.
if (this.compare(this.data[index], this.data[parent]) >= 0) {
break;
}
this.swap(index, parent);
index = parent;
}
}
// Restores the heap property by moving an element downward.
percolateDown(index) {
const n = this.size();
while (true) {
const left = 2 * index + 1;
const right = 2 * index + 2;
let best = index;
// Select the better child according to the comparator.
if (
left < n &&
this.compare(this.data[left], this.data[best]) < 0
) {
best = left;
}
if (
right < n &&
this.compare(this.data[right], this.data[best]) < 0
) {
best = right;
}
// The current node is already correctly ordered.
if (best === index) {
break;
}
this.swap(index, best);
index = best;
}
}
// Swaps two elements in the array.
swap(i, j) {
[this.data[i], this.data[j]] = [this.data[j], this.data[i]];
}
// Returns a copy of the internal array.
toArray() {
return [...this.data];
}
}