Step 3 of 4

Extract Minimum & Sift-Down

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.

To remove the minimum element (pop), we cannot simply shift the array as that would take $O(n)$ time.

Instead:

  1. Save the root element at index 0.
  2. Move the last element of the array to index 0 (this.data[0] = this.data.pop()).
  3. Call siftDown(0) to bubble the element downward by swapping with its smallest child until the min-heap property holds.
  4. Return the original minimum value.

Your build

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

Tests

1 case
calltypeexpectedresult
runOps([["push",20],["push",5],["push",10],["push",1],["push",30],["pop"],["pop"],["pop"],["pop"],["pop"],["pop"]])extracts elements in sorted ascending order[null,null,null,null,null,1,5,10,20,30,null]—

Hints

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

2 hints left