What is the time complexity of building a heap?

What is the time complexity of building a heap?

Approach: Explain the linear time complexity of the bottom-up approach.

O(n). While individual insertions are O(log n), the total cost of building a heap from an unordered array using 'sift down' operations is linear.

Follow-up: Why is it not O(n log n)?

Key concepts: sift down, O(n), complete binary tree.