Visualize Floyd's O(N) heap construction algorithm. Watch how sift-down from the last non-leaf builds a valid heap faster than N individual insertions.
Given an unsorted array, Floyd's algorithm builds a valid heap in O(N) time. Inserting each element one by one would cost O(N log N).
Floyd's insight: leaves don't need sifting. Starting from the last non-leaf and going up to root, each sift-down is bounded by the node's height, not the full tree height. The sum of all heights = O(N).
Last non-leaf = floor(n/2) - 1. Iterate from this index down to 0, sifting each node into place. Leaves (index ≥ n/2) are already valid heaps of size 1.
Sift-down is chosen because most nodes are near the bottom of the tree. In a full binary tree, half are leaves with height 0. Bubble-up would start from leaves and work upward, which is the opposite of what we want.
O(N) time and O(1) extra space. The input array becomes a valid heap in place.
Floyd's algorithm is the first step of Heap Sort. Pick a preset array and click Build to watch each sift-down run from the last non-leaf to the root.