Why is building a heap O(n) and not O(n log n)?

Adding n items one by one is O(n log n). The bottom-up build is O(n). Here's the intuition. In a complete tree, about half the nodes are leaves, and leaves need no work. A quarter of the nodes sit one level up and can move down at most 1 level. An eighth can move down at most 2 levels, and so on. Total work ≈ n/4 · 1 + n/8 · 2 + n/16 · 3 + ... That series adds up to a constant times n. Most nodes are near the bottom, where there's almost nowhere to fall. Only a handful of nodes near the top can move far.