MAX-HEAP                        MIN-HEAP
      100                               1
      / \                             / \
    19   36                          3   6
   /  \  / \                        / \ / \
  17  3 25  1                      5  9 8  7

Parent ≥ children                  Parent ≤ children
Root = largest element             Root = smallest element

Tree:                Array (1-indexed):
        100              index: 1   2   3   4   5   6   7
        / \              value:[100, 19, 36, 17,  3, 25,  1]
      19   36
     /  \  / \
   17   3 25   1

Index formulas (1-indexed):
  parent(i)      = floor(i / 2)
  left-child(i)  = 2 * i
  right-child(i) = 2 * i + 1

Index formulas (0-indexed — more common in code):
  parent(i)      = floor((i - 1) / 2)
  left-child(i)  = 2 * i + 1
  right-child(i) = 2 * i + 2

Insert 50 into max-heap [100, 19, 36, 17, 3, 25, 1]:

Step 1 — append at end (index 7):
  [100, 19, 36, 17, 3, 25, 1, 50]
              50 is at index 7, parent = floor((7-1)/2) = 3 → value 17

Step 2 — 50 > 17, swap:
  [100, 19, 36, 50, 3, 25, 1, 17]
              50 is at index 3, parent = floor((3-1)/2) = 1 → value 19

Step 3 — 50 > 19, swap:
  [100, 50, 36, 19, 3, 25, 1, 17]
              50 is at index 1, parent = 0 → value 100

Step 4 — 50 < 100, stop. Heap property restored.

Extract max from [100, 50, 36, 19, 3, 25, 1]:

Step 1 — swap root with last element:
  [1, 50, 36, 19, 3, 25, 100]   remove 100

Step 2 — sift down 1 at index 0:
  children: left=50 (idx 1), right=36 (idx 2), max child = 50
  1 < 50, swap → [50, 1, 36, 19, 3, 25]

Step 3 — sift down 1 at index 1:
  children: left=19 (idx 3), right=3 (idx 4), max child = 19
  1 < 19, swap → [50, 19, 36, 1, 3, 25]

Step 4 — 1 at index 3 has no children (left would be idx 7, out of bounds). Stop.

Result: [50, 19, 36, 1, 3, 25]   extracted max = 100

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

  size()    { return this.heap.length; }
  peek()    { return this.heap[0]; }        // max element, O(1)
  isEmpty() { return this.size() === 0; }

  // ── index helpers ──────────────────────────────────────
  parent(i) { return Math.floor((i - 1) / 2); }
  left(i)   { return 2 * i + 1; }
  right(i)  { return 2 * i + 2; }

  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  // ── insert  O(log n) ──────────────────────────────────
  insert(val) {
    this.heap.push(val);
    this.heapifyUp(this.size() - 1);
  }

  heapifyUp(i) {
    while (i > 0) {
      const p = this.parent(i);
      if (this.heap[p] < this.heap[i]) {
        this.swap(p, i);
        i = p;
      } else break;
    }
  }

  // ── extract max  O(log n) ────────────────────────────
  extractMax() {
    if (this.isEmpty()) return null;
    if (this.size() === 1) return this.heap.pop();

    const max = this.heap[0];
    this.heap[0] = this.heap.pop();     // move last to root
    this.heapifyDown(0);
    return max;
  }

  heapifyDown(i) {
    const n = this.size();
    while (true) {
      let largest = i;
      const l = this.left(i), r = this.right(i);
      if (l < n && this.heap[l] > this.heap[largest]) largest = l;
      if (r < n && this.heap[r] > this.heap[largest]) largest = r;
      if (largest === i) break;
      this.swap(i, largest);
      i = largest;
    }
  }
}

// ── MinHeap: just flip the comparison signs ────────────
class MinHeap extends MaxHeap {
  heapifyUp(i) {
    while (i > 0) {
      const p = this.parent(i);
      if (this.heap[p] > this.heap[i]) { this.swap(p, i); i = p; }
      else break;
    }
  }

  heapifyDown(i) {
    const n = this.size();
    while (true) {
      let smallest = i;
      const l = this.left(i), r = this.right(i);
      if (l < n && this.heap[l] < this.heap[smallest]) smallest = l;
      if (r < n && this.heap[r] < this.heap[smallest]) smallest = r;
      if (smallest === i) break;
      this.swap(i, smallest);
      i = smallest;
    }
  }

  extractMin() { return this.extractMax(); }  // same logic, different comparator
}

Why O(n) and not O(n log n)?

Nodes at height h can sink at most h levels.
  - n/2 nodes at height 0 (leaves):   0 work each
  - n/4 nodes at height 1:            1 swap each  →  n/4 · 1
  - n/8 nodes at height 2:            2 swaps each →  n/8 · 2
  - ...
  - 1 node at height log n:           log n swaps  →  1 · log n

Sum = n · Σ (h / 2^h) = n · 2 = O(n)   (geometric series)

function buildMaxHeap(arr) {
  const n = arr.length;
  // Last non-leaf is at index floor(n/2) - 1
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapifyDown(arr, n, i);
  }
  return arr;
}

function heapifyDown(arr, n, i) {
  let largest = i;
  const l = 2 * i + 1, r = 2 * i + 2;
  if (l < n && arr[l] > arr[largest]) largest = l;
  if (r < n && arr[r] > arr[largest]) largest = r;
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapifyDown(arr, n, largest);
  }
}

// Demo
const arr = [3, 1, 6, 5, 2, 4];
buildMaxHeap(arr);
// arr → [6, 5, 4, 1, 2, 3]

function heapSort(arr) {
  const n = arr.length;

  // Phase 1: build max-heap  O(n)
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--)
    heapifyDown(arr, n, i);

  // Phase 2: extract elements  O(n log n)
  for (let end = n - 1; end > 0; end--) {
    [arr[0], arr[end]] = [arr[end], arr[0]];  // move current max to sorted end
    heapifyDown(arr, end, 0);                  // re-heapify the shrunk heap
  }
  return arr;
}

heapSort([5, 3, 8, 4, 2]);
// → [2, 3, 4, 5, 8]

// Find K largest elements  — Time: O(n log k)  Space: O(k)
function topK(nums, k) {
  const minH = new MinHeap();

  for (const num of nums) {
    minH.insert(num);
    if (minH.size() > k) minH.extractMin();  // evict the smallest
  }

  // minH now contains the k largest elements
  return minH.heap;
}

topK([3, 2, 1, 5, 6, 4], 2);  // → [5, 6]  (heap order, not sorted)

// Why a min-heap?
// The root is the smallest of the top-k.
// When a new number arrives that is larger, it beats out the current minimum.
// This is more efficient than a max-heap of size n (O(n) space).

function findKthLargest(nums, k) {
  const minH = new MinHeap();
  for (const n of nums) {
    minH.insert(n);
    if (minH.size() > k) minH.extractMin();
  }
  return minH.peek();   // root = kth largest
}
// Time: O(n log k)   Space: O(k)

// Alternative: O(n) average with quickselect, but heap is simpler to code

Stream: 5, 15, 1, 3

After 5:   lo = [5]          hi = []          median = 5
After 15:  lo = [5]          hi = [15]         median = (5+15)/2 = 10
After 1:   lo = [5, 1]       hi = [15]         median = 5
After 3:   lo = [5, 3, 1]    hi = [15]         median = 5

lo stores lower half, hi stores upper half.
lo.peek() ≤ hi.peek() always.

class MedianFinder {
  constructor() {
    this.lo = new MaxHeap();   // lower half
    this.hi = new MinHeap();   // upper half
  }

  addNum(num) {
    // 1. Push into lo (always push to lo first)
    this.lo.insert(num);

    // 2. Balance: lo's max must be ≤ hi's min
    if (this.hi.size() > 0 && this.lo.peek() > this.hi.peek()) {
      this.hi.insert(this.lo.extractMax());
    }

    // 3. Keep sizes balanced: lo may have at most 1 extra element
    if (this.lo.size() > this.hi.size() + 1) {
      this.hi.insert(this.lo.extractMax());
    } else if (this.hi.size() > this.lo.size()) {
      this.lo.insert(this.hi.extractMin());
    }
  }

  findMedian() {
    if (this.lo.size() === this.hi.size()) {
      return (this.lo.peek() + this.hi.peek()) / 2;
    }
    return this.lo.peek();    // lo has the extra element
  }
}

// Demo
const mf = new MedianFinder();
mf.addNum(1);  mf.findMedian();  // 1
mf.addNum(2);  mf.findMedian();  // 1.5
mf.addNum(3);  mf.findMedian();  // 2

function kClosest(points, k) {
  // Max-heap by distance; evict farthest when size > k
  const dist = ([x, y]) => x * x + y * y;
  const maxH = [];   // [distance, point] pairs

  const siftDown = (i) => {
    const n = maxH.length;
    while (true) {
      let largest = i;
      const l = 2*i+1, r = 2*i+2;
      if (l < n && maxH[l][0] > maxH[largest][0]) largest = l;
      if (r < n && maxH[r][0] > maxH[largest][0]) largest = r;
      if (largest === i) break;
      [maxH[i], maxH[largest]] = [maxH[largest], maxH[i]];
      i = largest;
    }
  };
  const siftUp = (i) => {
    while (i > 0) {
      const p = Math.floor((i-1)/2);
      if (maxH[p][0] < maxH[i][0]) { [maxH[p], maxH[i]] = [maxH[i], maxH[p]]; i = p; }
      else break;
    }
  };

  for (const pt of points) {
    maxH.push([dist(pt), pt]);
    siftUp(maxH.length - 1);
    if (maxH.length > k) {
      maxH[0] = maxH.pop();
      siftDown(0);
    }
  }

  return maxH.map(([, pt]) => pt);
}
// Time: O(n log k)   Space: O(k)

function mergeKLists(lists) {
  // Min-heap stores [val, listIndex, node]
  const heap = [];

  const push = (item) => {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i-1)/2);
      if (heap[p][0] > heap[i][0]) { [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; }
      else break;
    }
  };

  const pop = () => {
    const min = heap[0];
    heap[0] = heap.pop();
    let i = 0;
    while (true) {
      let smallest = i;
      const l = 2*i+1, r = 2*i+2;
      if (l < heap.length && heap[l][0] < heap[smallest][0]) smallest = l;
      if (r < heap.length && heap[r][0] < heap[smallest][0]) smallest = r;
      if (smallest === i) break;
      [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
      i = smallest;
    }
    return min;
  };

  // Seed heap with the head of each list
  for (let i = 0; i < lists.length; i++)
    if (lists[i]) push([lists[i].val, i, lists[i]]);

  const dummy = { next: null };
  let cur = dummy;

  while (heap.length) {
    const [, idx, node] = pop();
    cur.next = node;
    cur = cur.next;
    if (node.next) push([node.next.val, idx, node.next]);
  }
  return dummy.next;
}
// Time: O(n log k) where n = total nodes, k = number of lists