Sift-up swaps in a binary heap

MediumProgramming & DSA~4m

A min-heap is stored as the array [1, 3, 2, 7, 8, 5, 9] (index $0$ is the root; the children of index $i$ are at $2i+1$ and $2i+2$ ). You insert the value 0 at the next free slot (index $7$ ) and sift it up to restore the heap. How many swaps does the sift-up perform?

Show hints (2)+

Parent of index $i$ is $\lfloor (i-1)/2 \rfloor$ ; swap while child $<$ parent.
Trace the path $7 \to 3 \to 1 \to 0$ .

Answer

Reveal answer →

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Hedge Fund Quant, Prop Trading

Sift-up swaps in a binary heap

Answer

Related questions