sift_down repairs a max-heap whose only fault is at one node: compare the node with the larger of its children and, if the child wins, swap them and continue from the child's position. Stop when the node is at least as large as both of its children, or when it has none.
Write sift_down(heap, start) which fixes the heap in place from index start and returns the array. Everything below start is already a valid max-heap.
Examples
Input: heap = [3, 9, 2, 8, 5], start = 0
Output: [9, 8, 2, 3, 5]
Explanation: 3 swaps with 9, then with 8, and then has no children left.
Input: heap = [7, 1, 2], start = 0
Output: [7, 1, 2]
Constraints
0 <= len(heap) <= 10**5,0 <= start < len(heap)whenever the list is not empty- Repair the list in place; the return value is the same list.
Goals
- Restore the heap property below one node
- Always swap with the larger child, never just any child that is bigger
- Stop as soon as the node is settled