A strong answer
Bottom-up heapify treats the array as a complete tree, skips the leaves (the second half of the array, already one-element heaps), and calls sift-down on each index from n/2 − 1 down to 0. When a node is processed, both of its subtrees are already heaps, so one sift-down makes its subtree a heap.
The naive bound is n/2 calls × O(log n) each = O(n log n), but that overcounts. A sift-down from a node costs at most the node's height above the bottom of the tree, and few nodes are high up: about n/2 nodes have height 0 and do nothing, n/4 have height 1, n/8 height 2, and so on. The total work is at most n/4 + 2n/8 + 3n/16 + ..., which sums to less than n, so heapify is O(n).
Building by n pushes is different: each push enters at the bottom and sifts up toward the root, so the many items at the bottom are the ones that can travel the full height. In the worst case, such as inserting values in decreasing order into a min-heap, that is Θ(n log n). The asymmetry is that heapify makes the many low nodes do little work and only the few high nodes do a lot.
Heap sort uses heapify (O(n)) and then n pops (O(n log n)), so the total is still O(n log n); heapify's linearity matters when you only pop a few items, as in partial sorting.
What the interviewer is listening for
- The bottom-up procedure and why it needs both subtrees to be heaps already.
- The level-by-level sum, or an equivalent argument that most nodes are near the bottom.
- The contrast with repeated insertion.
Common mistakes
- Accepting O(n log n) without noticing that work depends on height, not depth.
- Processing from the root down, which breaks sift-down's assumption.
- Claiming heap sort is O(n) because heapify is.