Show the max-heap that results from running build Heap on the subsequent values stored in an array:
10 5 12 3 2 1 8 7 9 4
To create a max-heap, we need to build the heap from the given array. The build Heap operation rearranges the elements in the array to satisfy the max-heap property.
Here are the steps to build the max-heap from the given array:
1. Start with the given array: [10, 5, 12, 3, 2, 1, 8, 7, 9, 4].
2. We start from the middle of the array and iterate back to the first element, applying the max-heapify operation on each element.
3. The max-heapify operation ensures that each subtree rooted at the current element is a max-heap.
Here is how the array transforms into a max-heap step by step:
1. Starting with the original array: [10, 5, 12, 3, 2, 1, 8, 7, 9, 4].
2. Max-heapify the subtree rooted at index 4 (element 2): [10, 5, 12, 3, 2, 1, 8, 7, 9, 4].
3. Max-heapify the subtree rooted at index 3 (element 3): [10, 5, 12, 7, 2, 1, 8, 3, 9, 4].
4. Max-heapify the subtree rooted at index 2 (element 12): [10, 5, 12, 7, 2, 1, 8, 3, 9, 4].
5. Max-heapify the subtree rooted at index 1 (element 5): [10, 7, 12, 5, 2, 1, 8, 3, 9, 4].
6. Max-heapify the subtree rooted at index 0 (element 10): [12, 7, 10, 5, 2, 1, 8, 3, 9, 4].
The resulting max-heap is: [12, 7, 10, 5, 2, 1, 8, 3, 9, 4].