Algorithms and Data Structures · Senior · Question 41 of 75
What is the complexity of building a binary heap from n unsorted elements with sift-down (heapify)?
- ✓Correct answer: O(n)
- 2O(log n)
- 3O(n log n)
Explanation
Most nodes are near the bottom and sift down only a little: half the nodes move 0 levels, a quarter 1 level and so on. The sum converges to O(n). Inserting elements one by one would be O(n log n).