AlgoScope

Heapify (Build Heap)

Sift every parent down, last one first. The whole build costs O(n), not O(n log n).

Heap algorithms, algorithm, intermediate
Building a min heap from 7 unordered values by sifting each parent down, starting with the last parent.1489276
Building a min heap from 7 unordered values by sifting each parent down, starting with the last parent.1489276

Binary Heap: Build a min heap

Start, step 1 of 12

These values are in no order. Sift every parent down, starting from the last one, and the whole thing becomes a min heap.

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

Sum of heights is O(n) not O(n log n).

Leads to

Topics that need this one first.

Taught by the same lesson

Binary Heap covers these too, in the same run.