Heap: Push and Pop
MediumA complete binary tree stored in an array. Push sifts the new value up, pop moves the last value to the root and sifts it down.
priority queuesift upsift down
TimeO(log n) per operation
SpaceO(n)
InputValues to push into a min heap
Empty
A min heap: every parent is at most its children.
1 / 26
push(v): append v, then
while v < parent: swap up
pop(): save root, move last element to root, then
while a child is smaller: swap down with the smaller child
Why it matters
Children of index i sit at 2i+1 and 2i+2, so no pointers are needed.
Keyboard
space play← → stepr restartctrl K search
More in Heap / Priority Queue
Next visualiser
Breadth First Search