Let’s Play with Heap Data Structure in JavaScript

Ready to unlock the secrets of heaps? Let's explore how they work, implement them in JavaScript, and use them to solve exciting problems.

Min-Heap Visualizer

Root Element

Heap is empty

Play

What’s a Heap Anyway?

Imagine you’re hosting a pizza party 🥳. Orders are pouring in, and you need to serve the hungriest guests first. Enter **heaps**, your new best friend for managing priorities.

A heap is a **special kind of tree** where elements are arranged by priority. The coolest part? They’re super fast for finding the highest or lowest priority item!

There are two types of heaps:

**Min-Heap**: Always keeps the smallest item at the top. Perfect for serving the most urgent tasks.
**Max-Heap**: Always keeps the largest item at the top. Great for leaderboard systems or finding top scores.

Let’s dive in and see how heaps can work for us!

Step 1: Understanding Heaps

So, how do heaps work? The secret lies in how they’re stored. Instead of complicated trees with pointers, we use **arrays**. Why? Because arrays make heaps super easy to manage!

Here’s how the relationships work in a heap:

**Parent of a node at index `i`**: (i - 1) // 2
**Left child of node `i`**: 2 * i + 1
**Right child of node `i`**: 2 * i + 2

Let’s see it in action with a **Min-Heap**.

Step 2: Building a Min-Heap

A **Min-Heap** makes sure the smallest element is always at the top. Imagine you’re serving pizzas 🍕, and you want to start with the smallest slice (the hungriest guest).

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(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = this.getParentIndex(index);
      if (this.heap[index] >= this.heap[parentIndex]) break;
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      index = parentIndex;
    }
  }

  remove() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const root = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown();
    return root;
  }

  heapifyDown() {
    let index = 0;
    while (index < this.heap.length) {
      const left = this.getLeftChildIndex(index);
      const right = this.getRightChildIndex(index);
      let smallest = index;

      if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
        smallest = left;
      }

      if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
        smallest = right;
      }

      if (smallest === index) break;
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }
}

Here’s what’s happening:

**`heapifyUp`**: Ensures the smallest value bubbles to the top after insertion.
**`heapifyDown`**: Rebalances the heap when the smallest value is removed.

Let’s test this with some data.

Step 3: Let’s Test It!

Let’s see how our Min-Heap handles a few numbers:

const heap = new MinHeap();
heap.insert(10);
heap.insert(15);
heap.insert(5);
heap.insert(20);

console.log(heap.remove()); // Outputs: 5
console.log(heap.remove()); // Outputs: 10

See how it always gives us the smallest value first? That’s the magic of a Min-Heap!

Wrapping Up

You’ve just unlocked a powerful tool for solving priority-based problems! From **task schedulers** to **leaderboards**, heaps have got you covered.

Want a challenge? Try implementing a **Max-Heap** or building a **priority queue** with your heap. The possibilities are endless. Go forth and conquer! 🚀