A heap is a complete binary tree where every parent is either smaller (min-heap) or larger (max-heap) than its children.
The root is always the min or max.
The tree is filled left to right, level by level.
Heaps are stored as arrays. For index i:
Relationship
Index formula
Parent
(i - 1) // 2
Left child
2 * i + 1
Right child
2 * i + 2
// means integer division, divide and round down.
Insert node
Insert new node at the end of the array, and then bubble up until the heap property is restored.
js
// Insert a value into the heapfunction insert(heap, value) { // Add at the end of the array heap.push(value); // Restore the heap property bubbleUp(heap, heap.length - 1);}
Time: O(log n)
Bubble up
These are the two fundamental operations used to restore the heap property after modifying a heap: bubbling up and sinking down.
Bubble up is used after inserting a new element at the end of the heap.
Moves the new element up the tree by repeatedly swapping it with its parent, until the heap property is restored.
Start at the newly inserted element's index i.
Compare it with its parent at (i - 1) // 2.
If the parent violates heap property, swap them.
Move i to the parent's index and repeat.
Stop when heap property is restored, or when you reach the root.
Full-Stack AI Developer Roadmap
From HTML & CSS to working with AI models, all in one structured roadmap.
www.thedevspace.io
js
function bubbleUp(heap, i) { while (i > 0) { const parent = (i - 1) >> 1; // Heap property restored, stop if (heap[parent] <= heap[i]) break; // Swap with the parent and keep going up [heap[parent], heap[i]] = [heap[i], heap[parent]]; i = parent; }}
Time: O(log n) -> the height of the tree.
Remove node
Remove a node by swapping it with the last element in the array, then restoring the heap property by bubbling up or sinking down as necessary.
js
// Remove a value from the heapfunction remove(heap, value) { // Find the value's index const i = heap.indexOf(value); if (i === -1) return false; // Swap with the last element and remove it const last = heap.pop(); if (i < heap.length) { heap[i] = last; // Restore the heap property in both directions bubbleUp(heap, i); sinkDown(heap, i); } return true;}
Time: O(n) to find the value, O(log n) to restore the heap.
Sink down
Used after removing the root or heapifying an array.
It moves an element down the tree by repeatedly swapping it with its smallest (min-heap) or largest (max-heap) child until the heap property is restored.
Start at the element's index i.
Find the smallest or largest child at 2i + 1 or 2i + 2.
If the element is not the smallest/largest, swap with that child.
Move i to the child's index and repeat.
Stop when heap property is restored, or when it becomes a leaf.
js
function sinkDown(heap, i) { while (true) { const left = 2 * i + 1; const right = 2 * i + 2; let smallest = i; if (left < heap.length && heap[left] < heap[smallest]) smallest = left; if (right < heap.length && heap[right] < heap[smallest]) smallest = right; // Heap property restored, stop
DSA Heaps | TheDevSpace
Time: O(log n) -> the height of the tree.
Extract min/max
Remove the root, move the last element to the top, then sink down.
js
// Remove and return the smallest elementfunction extractMin(heap) { const min = heap[0]; const last = heap.pop(); if (heap.length > 0) { // Move the last element to the root heap[0] = last; // Restore the heap property sinkDown(heap, 0); } return min;}
Time: O(log n). For a max-heap, flip the comparisons.
Heapify an array
Build a heap from an unsorted array in O(n) by sinking down from the last parent.
js
// Turn an unsorted array into a heapfunction heapify(nums) { // Start from the last parent and sink each one down for (let i = (nums.length >> 1) - 1; i >= 0; i--) { sinkDown(nums, i); } return nums;}
Heapify is O(n), faster than inserting n elements one by one (O(n log n)).
if (smallest === i) break;
// Swap with the smallest child and keep going down
