Typorithm · medium

Heap Insert (Sift Up)

heap-sift-upheapsbinary-heapsift-uparray-tree

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Heap Insert (Sift Up)

Heaps

JavaScript has no built-in heap; insert by appending, then sift the value up while it is smaller than its parent.

A binary heap is stored in a flat array where a node at index i has parent (i - 1) >> 1.

Insertion appends the value to the end, then bubbles it up while it violates heap order.

Each swap moves the value one level toward the root, so insertion is O(log n).

Parent index is (i - 1) >> 1.

Append, then sift up.

Stop when parent <= child.

class MinHeap {
  constructor() {
    this.data = [];
  }

  push(val) {
    this.data.push(val);
    let i = this.data.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.data[parent] <= this.data[i]) {
        break;
      }
      [this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
      i = parent;
    }
  }
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Append at end

A new value first lands at the last array slot.

this.data.push(val)

2. Parent index

In a 0-based array heap, a node's parent is (i - 1) >> 1.

const parent = (i - 1) >> 1

3. Heap order holds

Stop once the parent is no larger than the child.

if (this.data[parent] <= this.data[i]) {
        break;
      }

4. Swap upward

Destructuring swaps the child up toward the root.

[this.data[parent], this.data[i]] = [this.data[i], this.data[parent]]

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.