Build a Heap from an Array (Heapify)

The problem. Given an array nums, rearrange its values in place so that it becomes a valid min-heap — every parent nums[i] is less than or equal to its children nums[2i + 1] and nums[2i + 2] — and return it. Any valid heap is accepted.

Example

nums = [9, 4, 7, 1, 8, 2]   ->  [1, 4, 2, 9, 8, 7]   (other valid heaps are fine too)
nums = [3, 2, 1]            ->  [1, 2, 3]
nums = [1, 2, 3, 4]         ->  [1, 2, 3, 4]         (already a heap: nothing moves)

Fun fact: a sorted array is always a valid min-heap — every parent sits at a smaller index than its children. So sorting solves this in O(n log n). The question is whether we can do better.