Speed:

Min Heap

Insert: O(log n)Extract Min: O(log n)Peek: O(1)

🔻How Min Heap Works

A Min Heap is a complete binary tree where every parent node is less than or equal to its children. The minimum element is always at the root, making it perfect for priority queues and efficiently finding the smallest element.

Key properties of Min Heap:

Heap Property: Parent ≤ children for all nodes
Complete Tree: All levels filled except possibly the last
Array Representation: Parent at index i, children at 2i+1 and 2i+2
Root Minimum: Smallest element always at index 0
Efficient Operations: Insert and extract in O(log n) time

💻Implementation

// Min Heap Implementation
class MinHeap {
  constructor() {
    this.heap = [];
  }
  
  // Helper methods
  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }
  
  getLeftChildIndex(index) {
    return 2 * index + 1;
  }
  
  getRightChildIndex(index) {
    return 2 * index + 2;
  }
  
  hasParent(index) {
    return this.getParentIndex(index) >= 0;
  }
  
  hasLeftChild(index) {
    return this.getLeftChildIndex(index) < this.heap.length;
  }
  
  hasRightChild(index) {
    return this.getRightChildIndex(index) < this.heap.length;
  }
  
  parent(index) {
    return this.heap[this.getParentIndex(index)];
  }
  
  leftChild(index) {
    return this.heap[this.getLeftChildIndex(index)];
  }
  
  rightChild(index) {
    return this.heap[this.getRightChildIndex(index)];
  }
  
  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
  }
  
  // Insert element
  insert(value) {
    this.heap.push(value);
    this.heapifyUp();
  }
  
  // Remove and return minimum element
  extractMin() {
    if (this.heap.length === 0) 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;
  }
  
  // Get minimum without removing
  peek() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }
  
  // Restore heap property upward
  heapifyUp() {
    let index = this.heap.length - 1;
    while (this.hasParent(index) && this.parent(index) > this.heap[index]) {
      this.swap(this.getParentIndex(index), index);
      index = this.getParentIndex(index);
    }
  }
  
  // Restore heap property downward
  heapifyDown() {
    let index = 0;
    while (this.hasLeftChild(index)) {
      let smallerChildIndex = this.getLeftChildIndex(index);
      
      if (this.hasRightChild(index) && 
          this.rightChild(index) < this.leftChild(index)) {
        smallerChildIndex = this.getRightChildIndex(index);
      }
      
      if (this.heap[index] < this.heap[smallerChildIndex]) {
        break;
      }
      
      this.swap(index, smallerChildIndex);
      index = smallerChildIndex;
    }
  }
  
  size() {
    return this.heap.length;
  }
  
  isEmpty() {
    return this.heap.length === 0;
  }
}

📊Operations Analysis

Time Complexity

• Insert: O(log n) - heapify up
• Extract Min: O(log n) - heapify down
• Peek: O(1) - just return root
• Build Heap: O(n) from array

Space Complexity

• Storage: O(n) for n elements
• Array-based: No extra pointer overhead
• In-place: Operations use O(1) extra space
• Cache-friendly: Good memory locality

🎯 Applications

• Priority Queues: Process scheduling, event simulation
• Dijkstra's Algorithm: Shortest path finding
• Huffman Coding: Data compression algorithms
• A* Search: Pathfinding in games and robotics
• Median Finding: Using two heaps (min + max)

⚡ Advantages

• Efficient min access: O(1) to find minimum
• Logarithmic operations: Insert/delete in O(log n)
• Memory efficient: Array-based implementation
• Simple structure: Easy to implement and understand
• Cache performance: Good spatial locality