Answer

Floyd's bottom-up heapify algorithm builds a max-heap in O(n) time by starting from the last non-leaf node and calling sift-down on each node toward the root. Although each sift-down is O(log n) in the worst case, most nodes are near the leaves where sift-down is very shallow, and the summed work across all levels converges to a linear bound. This is more efficient than inserting elements one by one, which would take O(n log n).