Heap Extract Min

Remove the minimum from a binary min-heap and restore the heap property by sifting the new root down.

Time O(log n) Space O(1) Binary Heap extractMin

How it works

Remove the minimum from a binary min-heap and restore the heap property by sifting the new root down.

Implementation

function heapExtractMinOp(state) {
  const values = state.values;
  const n = values.length;
  if (n === 0) {
    reportNotFound();
    return;
  }
  const min = values[0];
  removeNode(0, min);
  const last = values[n - 1];
  values.length = n - 1;
  if (values.length === 0) {
    finish(min);
    return;
  }
  values[0] = last;
  updateNode(0, last);
  const size = values.length;
  let i = 0;
  while (true) {
    let smallest = i;
    const l = 2 * i + 1;
    const r = 2 * i + 2;
    if (l < size && values[l] < values[smallest]) {
      smallest = l;
    }
    if (r < size && values[r] < values[smallest]) {
      smallest = r;
    }
    compareKeys(i, smallest);
    if (smallest === i) {
      finish(min);
      return;
    }
    const tmp = values[i];
    values[i] = values[smallest];
    values[smallest] = tmp;
    swapNodes(i, smallest);
    i = smallest;
  }
}