Min Heap and Max Heap in JavaScript

Introduction

In the world of algorithms and data structures, heaps play a crucial role. Two common types of heaps are Min Heap and Max Heap, each with its unique characteristics and use cases. In this blog post, we’ll delve into the concepts of Min Heap and Max Heap, exploring their structures, applications, and implementation in JavaScript.

Heaps Overview

What is a Heap?

A heap is a specialized tree-based data structure that satisfies the heap property. In a heap, each node follows a specific order concerning its parent and children. This property ensures efficient retrieval of the minimum or maximum element from the heap.

Heap Property

• Min Heap: In a Min Heap, the value of each node is less than or equal to the values of its children. The minimum value is at the root.
• Max Heap: In a Max Heap, the value of each node is greater than or equal to the values of its children. The maximum value is at the root.

Min Heap

Characteristics

• Root Element: The smallest element in the heap.
• Parent-Child Relationship: The value of each node is less than or equal to its children.
• Common Operations: Extracting the minimum element, inserting a new element.

Use Cases

• Priority Queues: Min Heaps are used to implement priority queues where elements with higher priority (lower value) are served before elements with lower priority.
• Dijkstra’s Algorithm: Min Heaps help optimize Dijkstra’s algorithm for finding the shortest path in a graph.

Javascript Implimantaion

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

  // Add an element to the min heap
  push(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  // Remove and return the maximum element from the min heap
  pop() {
    if (this.heap.length === 0) {
      return null;
    }

    if (this.heap.length === 1) {
      return this.heap.pop();
    }

    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.sinkDown(0);
    return max;
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[index] >= this.heap[parentIndex]) { // Change to >=
        break;
      }
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      index = parentIndex;
    }
  }

  sinkDown(index) {
    const leftChildIndex = 2 * index + 1;
    const rightChildIndex = 2 * index + 2;
    let minIndex = index;

    if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] < this.heap[minIndex]) { // Change to <
      minIndex = leftChildIndex;
    }

    if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[minIndex]) { // Change to <
      minIndex = rightChildIndex;
    }

    if (index !== minIndex) {
      [this.heap[index], this.heap[minIndex]] = [this.heap[minIndex], this.heap[index]];
      this.sinkDown(minIndex);
    }
  }
}

// Example usage of MinHeap (Mean Heap)
const minHeap = new MinHeap();
minHeap.push(4);
minHeap.push(10);
minHeap.push(8);
minHeap.push(5);
console.log(minHeap.pop()); // Output: 4 (since it's now a min heap)

Max Heap

Characteristics

• Root Element: The largest element in the heap.
• Parent-Child Relationship: The value of each node is greater than or equal to its children.
• Common Operations: Extracting the maximum element, inserting a new element.

Use Cases

• Job Scheduling: Max Heaps can be utilized for job scheduling, where tasks with higher priority (larger value) are processed first.
• Huffman Coding: Max Heaps assist in the construction of Huffman trees used in data compression algorithms.

Conclusion

Understanding Min Heap and Max Heap is fundamental for solving various algorithmic problems efficiently. In JavaScript, these heaps can be implemented using arrays and customized methods. Whether you’re preparing for a front-end interview or simply looking to deepen your knowledge, mastering these heap structures will undoubtedly enhance your problem-solving skills.

Happy coding! 🚀