What goes in the blank?
# heapify: sift down from the last parent to the root
for i in range(n // 2 - 1, -1, -1):
sift_down(a, i)
# total time: O(____)
Answer: n
Most nodes sit near the bottom and sift only a little, so bottom-up heap construction sums to O(n), not O(n log n).
Play Problem Solving ▸