Typorithm · medium

Build Heap (Heapify)

build-heapheapsheapifybottom-uplinear-build

Saved on this device

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

Step 1 of 8 · intro card

Learn Build Heap (Heapify)

Heaps

Heapify an array in O(n) by sifting down every internal node, starting from the last parent up to the root.

Inserting n elements one by one builds a heap in O(n log n), but bottom-up heapify does it in O(n).

Leaves are already valid one-element heaps, so only internal nodes — indices 0..(n >> 1) - 1 — need sifting.

Processing parents from the bottom up guarantees each node's children are already heaps when it sinks.

Start at the last parent (n >> 1) - 1.

Sift down each node up to the root.

Linear O(n) total, not O(n log n).

function heapify(data) {
  const n = data.length;
  for (let i = (n >> 1) - 1; i >= 0; i -= 1) {
    siftDown(data, i, n);
  }
  return data;
}

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

The last internal node is at (n >> 1) - 1; leaves need no sifting.

let i = (n >> 1) - 1

Process parents from the bottom row up to the root.

i >= 0; i -= 1

Sift each node down so its subtree becomes a valid heap.

siftDown(data, i, n)

Read the concept map and follow the code breakdown.

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

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