Rearrange an Array Into a Max Heap
Rearrange an Array Into a Max Heap
Everything in the lab is a MIN heap. This question flips it. Complete max_heapify_down and build_max_heap so that a plain array of ints is rearranged into a MAX heap: every parent is greater than or equal to its children, so the LARGEST value ends up at index 0.
Reminder: a max heap is a min heap with every comparison turned around. It is stored the same way: a complete binary tree in an array, filled row by row with no gaps. For the value at index i, the parent is at (i - 1) / 2 and the children are at 2 * i + 1 and 2 * i + 2. There is no struct in this question, only the array and a count, so a child exists when its index is less than count.
max_heapify_down on index 0 of 2 9 7 4 8 (count 5):
the LARGER child of 2 is 9 the larger child of 2 is 8 no children: stop
2 < 9, swap 2 < 8, swap
2 9 9
/ \ / \ / \
9 7 2 7 8 7
/ \ / \ / \
4 8 4 8 4 2
2 9 7 4 8 9 2 7 4 8 9 8 7 4 2In a min heap a value sinks by swapping with its SMALLER child. Here it sinks by swapping with its LARGER child, and it stops when it is greater than or equal to that child. build_max_heap then uses the same bottom-up idea as the lab's heapify: sink every parent, from the last parent at count / 2 - 1 back to index 0.
Requirements:
1. max_heapify_down(values, count, i): while index i has a left child, pick the larger child (the right one only when it exists and is larger); stop when values[i] is greater than or equal to it, otherwise swap the two and continue from the child.
2. build_max_heap(values, count): call max_heapify_down for every index from count / 2 - 1 down to 0.
3. Never read or write a slot at index count or beyond.
Do NOT write a main function.
Expected Output:
after: 9 8 7 4 2 | 99= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...