Speed:

Max Heap

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

🔺How Max Heap Works

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

Key properties of Max 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 Maximum: Largest element always at index 0
Efficient Operations: Insert and extract in O(log n) time

💻Implementation

// Max Heap Implementation
class MaxHeap {
  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 maximum element
  extractMax() {
    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.heapifyDown();
    return max;
  }
  
  // Get maximum 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 largerChildIndex = this.getLeftChildIndex(index);
      
      if (this.hasRightChild(index) && 
          this.rightChild(index) > this.leftChild(index)) {
        largerChildIndex = this.getRightChildIndex(index);
      }
      
      if (this.heap[index] > this.heap[largerChildIndex]) {
        break;
      }
      
      this.swap(index, largerChildIndex);
      index = largerChildIndex;
    }
  }
  
  size() {
    return this.heap.length;
  }
  
  isEmpty() {
    return this.heap.length === 0;
  }
}

📊Operations Analysis

Time Complexity

• Insert: O(log n) - heapify up
• Extract Max: 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: Task scheduling, event simulation
• Heap Sort: In-place O(n log n) sorting algorithm
• Graph Algorithms: Dijkstra's shortest path
• Selection Problems: Finding k largest elements
• Median Finding: Using two heaps (max + min)

⚡ Advantages

• Efficient max access: O(1) to find maximum
• 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