How to Implement Heap in JavaScript: Simple Guide and Example

To implement a heap in JavaScript, create a class that manages an array and provides methods to insert elements and remove the root while maintaining the heap property. Use helper functions to heapify up or down to keep the structure balanced as a min-heap or max-heap.

Syntax

A heap is usually implemented as a class with an internal array to store elements. Key methods include:

• insert(value): Adds a new value and adjusts the heap.
• extract(): Removes and returns the root (min or max) and rebalances.
• heapifyUp() and heapifyDown(): Helper methods to maintain heap order.

The array index relationships are: parent at Math.floor((index - 1) / 2), left child at 2 * index + 1, right child at 2 * index + 2.

javascript

class Heap {
  constructor() {
    this.items = [];
  }

  insert(value) {
    this.items.push(value);
    this.heapifyUp();
  }

  extract() {
    if (this.items.length === 0) return null;
    const root = this.items[0];
    const end = this.items.pop();
    if (this.items.length > 0) {
      this.items[0] = end;
      this.heapifyDown();
    }
    return root;
  }

  heapifyUp() {
    // To be implemented
  }

  heapifyDown() {
    // To be implemented
  }
}

Example

This example shows a min-heap implementation with working heapifyUp and heapifyDown methods. It inserts numbers and extracts the smallest value each time.

javascript

class MinHeap {
  constructor() {
    this.items = [];
  }

  insert(value) {
    this.items.push(value);
    this.heapifyUp();
  }

  extract() {
    if (this.items.length === 0) return null;
    const root = this.items[0];
    const end = this.items.pop();
    if (this.items.length > 0) {
      this.items[0] = end;
      this.heapifyDown();
    }
    return root;
  }

  heapifyUp() {
    let index = this.items.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.items[parentIndex] <= this.items[index]) break;
      [this.items[parentIndex], this.items[index]] = [this.items[index], this.items[parentIndex]];
      index = parentIndex;
    }
  }

  heapifyDown() {
    let index = 0;
    const length = this.items.length;
    while (true) {
      let left = 2 * index + 1;
      let right = 2 * index + 2;
      let smallest = index;

      if (left < length && this.items[left] < this.items[smallest]) {
        smallest = left;
      }
      if (right < length && this.items[right] < this.items[smallest]) {
        smallest = right;
      }
      if (smallest === index) break;

      [this.items[index], this.items[smallest]] = [this.items[smallest], this.items[index]];
      index = smallest;
    }
  }
}

const heap = new MinHeap();
heap.insert(10);
heap.insert(5);
heap.insert(14);
heap.insert(2);
console.log(heap.extract()); // 2
console.log(heap.extract()); // 5
console.log(heap.extract()); // 10
console.log(heap.extract()); // 14
console.log(heap.extract()); // null

Output

2
5
10
14
null

Common Pitfalls

Common mistakes when implementing heaps include:

• Not updating the index correctly during heapifyUp or heapifyDown, causing infinite loops.
• Mixing min-heap and max-heap logic without adjusting comparison operators.
• Forgetting to handle empty heap cases in extract.
• Using incorrect parent or child index calculations.

javascript

class WrongHeap {
  constructor() {
    this.items = [];
  }

  insert(value) {
    this.items.push(value);
    this.heapifyUp();
  }

  heapifyUp() {
    let index = this.items.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2); // Corrected: should be Math.floor((index - 1) / 2)
      if (this.items[parentIndex] <= this.items[index]) break;
      [this.items[parentIndex], this.items[index]] = [this.items[index], this.items[parentIndex]];
      index = parentIndex;
    }
  }
}

// Correct parent index calculation:
// let parentIndex = Math.floor((index - 1) / 2);

Quick Reference

• Parent index: Math.floor((i - 1) / 2)
• Left child index: 2 * i + 1
• Right child index: 2 * i + 2
• Insert: Add to end, then heapifyUp
• Extract: Remove root, replace with last, then heapifyDown
• Min-heap: Parent <= children
• Max-heap: Parent >= children

Key Takeaways

Implement a heap using an array and maintain heap order with heapifyUp and heapifyDown methods.

Use correct parent and child index formulas to navigate the heap structure.

Handle edge cases like empty heap extraction to avoid errors.

Choose comparison operators carefully to implement min-heap or max-heap behavior.

Test your heap by inserting and extracting elements to verify correct ordering.