If you build a heap bottom-up (heapify), most nodes are near the leaves and move only a small distance. The total work across all nodes forms a decreasing series, which sums to O(n). Doing n inserts one-by-one is O(n log n), but bottom-up heapify is O(n).