Heap Insert

Insert a value into a binary min-heap and restore the heap property by sifting it up.

Time O(log n) Space O(n) Binary Heap insert

How it works

Insert a value into a binary min-heap and restore the heap property by sifting it up.

Implementation

function heapInsertOp(state, value) {
  const values = state.values;
  let i = values.length;
  values[i] = value;
  insertNode(i, value);
  while (i > 0) {
    const parent = Math.floor((i - 1) / 2);
    compareKeys(i, parent);
    if (values[i] < values[parent]) {
      const tmp = values[i];
      values[i] = values[parent];
      values[parent] = tmp;
      swapNodes(i, parent);
      i = parent;
    } else {
      finish(i);
      return;
    }
  }
  finish(i);
}