Heapify (Build Heap)
Sift every parent down, last one first. The whole build costs O(n), not O(n log n).
Binary Heap: Build a min heap
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).
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Binary Heap covers these too, in the same run.