A max-heap is built from the array [3, 9, 2, 1, 4, 5] using standard bottom-up heapify. What is the resulting array?

Bottom-up heapify starts from the last non-leaf node (index 2, value 2) and works up to the root. Heapify(index 2, value 2): children are index 5 (value 5) → swap 2 and 5 → array becomes [3,9,5,1,4,2]. Heapify(index 1, value 9): children are index 3 (1) and index 4 (4), 9 is already largest, no swap. Heapify(index 0, value 3): children are index 1 (9) and index 2 (5); largest child is 9 → swap 3 and 9 → [9,3,5,1,4,2]; continue heapifying down at index 1 (now value 3): children are index 3 (1) and index 4 (4); largest is 4 → swap → final array: [9,4,5,1,3,2].