Step 4 of 4

Linear-Time Heapify

You start from the build so far — your own work where you have written it, the reference build where you have not. Either way this step stands on its own.

Inserting $n$ elements one-by-one with push takes $O(n \log n)$ time.

By running siftDown in reverse level order — starting at the last internal non-leaf node ($\lfloor n/2 \rfloor - 1$) down to index 0 — we can build a valid min-heap in $O(n)$ linear time!

Implement heapify(arr):

  • Store a copy of arr in this.data.
  • Iterate from Math.floor(this.data.length / 2) - 1 down to 0, calling this.siftDown(i).

Your build

Running is free — Submit is what records the step. Or press ⌘↩

Tests

1 case
calltypeexpectedresult
runOps([["heapify",[9,4,7,1,3,6,5]],["peek"],["pop"],["pop"],["pop"]])converts unsorted array into valid min-heap[[1,3,5,4,9,6,7],1,1,3,4]—

Hints

Stuck? Hints open one at a time, each giving a little more away.

2 hints left