Floyd's method turns any array into a max-heap in place. The second half of the array holds the leaves, and a leaf is already a heap of one, so only the indices from \lfloor n/2 \rfloor - 1 down to 0 need work — each one sifted down into the heaps its children already are.
Write build_heap(nums) returning a new list holding the result of that procedure, leaving the input untouched. Sift-down must always swap with the larger child.
Examples
Input: nums = [4, 10, 3, 5, 1]
Output: [10, 5, 3, 4, 1]
Input: nums = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 1, 2]
Constraints
0 <= len(nums) <= 10**5, values are integers- The order of the result is exactly the one this procedure produces; another valid heap of the same values is not accepted.
Goals
- Turn an arbitrary array into a heap without inserting one item at a time
- Start at the last node that has children and work backwards
- See why this costs O(n) and not O(n log n)