Implementing Heaps with NodeJS and Javascript

Need the smallest (or largest) item without scanning the whole list? A heap keeps it at the root in O(log n) per insert/remove — basis for priority queues and heapsort.

What you'll learn:

• Min-heap vs max-heap
• Array representation (parent/child indices)
• insert, heapify, extract-min
• Trees without pointer nodes

Prerequisites: trees (ep. 6) and hash tables (ep. 8).

Binary heap: min-heap in an array

Alright, Heaps are trees. What makes them special is that a Heap follows a specific pre-defined structure, and that structure is what gives it all its power. Heap trees are used in most cases to manage collections of data that need some kind of priority, and also as the backbone of efficient sorting algorithms.

A Heap is a binary tree—do you remember what that is? If not, go back to the Trees post... (just kidding) but in short, binary trees are those where all elements smaller than the first node go to one side, and all larger ones go to the other side. Heaps follow the same idea, but with a twist.

graph TD
  A["2 (root / min)"]
  A --> B["10"]
  A --> C["5"]
  B --> D["20"]
  B --> E["30"]
  C --> F["15"]

In a Heap, the root node is always the largest or the smallest value compared to everything else in the tree. That gives us two well-known flavors: max-heap (root is the largest) and min-heap (root is the smallest). These definitions drive how insertions and removals work, always keeping the most "important" element right at the top—so access to it is always O(1).

Hands-on

First The Theory

Before we dive into code, here is the detail that makes Heaps really elegant: we don't need a tree of objects to implement them. We can use a plain array instead, using index math to figure out where each parent and child lives:

• Parent of index i → Math.floor((i - 1) / 2)
• Left child of index i → 2 * i + 1
• Right child of index i → 2 * i + 2

That's it. No node.left or node.right pointers needed. The array is the tree.

Now The Practice

Open your favourite IDE or VSCode, create a file called heaps.js and paste the code below:

class MinHeap {
  constructor() {
    this.heap = []
  }
 
  getParentIndex(i) {
    return Math.floor((i - 1) / 2)
  }
  getLeftChildIndex(i) {
    return 2 * i + 1
  }
  getRightChildIndex(i) {
    return 2 * i + 2
  }
 
  insert(key) {
    this.heap.push(key)
    this.heapifyUp()
  }
}

Breaking it down:

• MinHeap is the class that will bring our Heap to life.
• Inside constructor we initialise the heap array—this flat array is our actual tree.
• getParentIndex, getLeftChildIndex, and getRightChildIndex are helper functions that calculate positions using the index math we talked about above.
• insert pushes the new value to the end of the array and then calls heapifyUp to bubble it up to its correct spot.

With just this we can't see the magic yet. We still need a couple more functions. Let's add them one by one.

heapifyUp adjusts the heap upwards—after inserting a new value, it bubbles the element up the tree until it finds the right position. Paste this right after insert:

  heapifyUp() {
    let index = this.heap.length - 1
    while (index !== 0 && this.heap[this.getParentIndex(index)] > this.heap[index]) {
      ;[this.heap[this.getParentIndex(index)], this.heap[index]] = [
        this.heap[index],
        this.heap[this.getParentIndex(index)],
      ]
      index = this.getParentIndex(index)
    }
  }

heapifyDown adjusts the heap downwards—after removing the root, everything needs to shift down to its correct spot. Paste this right after heapifyUp:

  heapifyDown() {
    let index = 0
    while (this.getLeftChildIndex(index) < this.heap.length) {
      let smallerChildIndex = this.getLeftChildIndex(index)
      if (
        this.getRightChildIndex(index) < this.heap.length &&
        this.heap[this.getRightChildIndex(index)] < this.heap[smallerChildIndex]
      ) {
        smallerChildIndex = this.getRightChildIndex(index)
      }
      if (this.heap[index] < this.heap[smallerChildIndex]) break
      ;[this.heap[index], this.heap[smallerChildIndex]] = [
        this.heap[smallerChildIndex],
        this.heap[index],
      ]
      index = smallerChildIndex
    }
  }

extractMin removes the smallest element from the root, replaces it with the last element in the array, then calls heapifyDown to restore order. Paste this after heapifyDown:

  extractMin() {
    if (!this.heap.length) return null
    if (this.heap.length === 1) return this.heap.pop()
 
    const min = this.heap[0]
    this.heap[0] = this.heap.pop()
    this.heapifyDown()
    return min
  }

ALMOST DONE, I PROMISE!

With everything in place, let's add some console.log calls, create a few elements, and see if the heap is behaving as expected. Paste this after the MinHeap class:

const minHeap = new MinHeap()
 
minHeap.insert(10)
console.log(`minHeap insert 10:`, { heap: minHeap.heap })
 
minHeap.insert(5)
console.log(`minHeap insert 5:`, { heap: minHeap.heap })
 
minHeap.insert(15)
console.log(`minHeap insert 15:`, { heap: minHeap.heap })
 
minHeap.insert(20)
console.log(`minHeap insert 20:`, { heap: minHeap.heap })
 
minHeap.insert(30)
console.log(`minHeap insert 30:`, { heap: minHeap.heap })
 
minHeap.insert(2)
console.log(`minHeap insert 2:`, { heap: minHeap.heap })

Breaking it down:

• We create a new Heap with const minHeap = new MinHeap().
• We insert a handful of values and log the state of the array after each one.

Now for the last part—let's verify extractMin actually gives us the smallest value each time. Add this after the inserts:

console.log(`1st extraction of current min value:`, {
  currentMinValue: minHeap.extractMin(),
  heap: minHeap.heap,
})
 
console.log(`2nd extraction of current min value:`, {
  currentMinValue: minHeap.extractMin(),
  heap: minHeap.heap,
})
 
console.log(`3rd extraction of current min value:`, {
  currentMinValue: minHeap.extractMin(),
  heap: minHeap.heap,
})

Run the file:

node heaps.js

If everything went well, you should see something like this:

minHeap insert 10: { heap: [ 10 ] }
minHeap insert 5: { heap: [ 5, 10 ] }
minHeap insert 15: { heap: [ 5, 10, 15 ] }
minHeap insert 20: { heap: [ 5, 10, 15, 20 ] }
minHeap insert 30: { heap: [ 5, 10, 15, 20, 30 ] }
minHeap insert 2: { heap: [ 2, 10, 5, 20, 30, 15 ] }
1st extraction of current min value: { currentMinValue: 2, heap: [ 5, 10, 15, 20, 30 ] }
2nd extraction of current min value: { currentMinValue: 5, heap: [ 10, 20, 15, 30 ] }
3rd extraction of current min value: { currentMinValue: 10, heap: [ 15, 20, 30 ] }

AWESOME!

Can you spot what happened when we inserted 2? It immediately bubbled up to the root position because it was smaller than everything else. And each extractMin call peeled off the current smallest, then heapifyDown restored the heap order.

Why is 10 after 2 when we insert it, but not directly after 5 after the first extraction?

That's the heap property at work—it only guarantees the root is the minimum, not that the rest of the array is fully sorted. The internal arrangement is a side-effect of the heapifyDown path, not a sorted array. Play around with different insertion orders and see what you get!

Edge cases: heapify after every insert

Skipping heapify after push breaks the heap property — index 0 is not the true minimum.

Heaps only for numbers? No — compare on a priority field or custom comparator.

TL;DR — Heap

Next steps

• Priority queues (ep. 10)
• Sorting arrays (ep. 15)

Before you go

Built a heap for scheduling or alerts? Share your heapify edge case in the comments.