Build a Heap From an Array With min_heap_heapify
Build a Heap From an Array With min_heap_heapify
Complete min_heap_heapify. It adds every value of a plain array to the heap and leaves a valid min heap. It returns true when all the values fit, and false (adding nothing) when they do not. heapify_down is already written for you.
Reminder: how this min heap is stored. A min_heap is a struct with three fields: capacity (the most values it can hold), count (how many it holds now) and values (a pointer to an array made with malloc). The heap is a complete binary tree kept in that array, filled row by row with no gaps, so only slots 0 to count - 1 are in use. Every parent is smaller than or equal to its children, so the smallest value is always at index 0. 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.
You could insert the values one at a time, but there is a faster way. Copy them all onto the end of the array first, ignoring the heap rule. Then repair the tree from the bottom up: call heapify_down on the LAST PARENT, then the parent before it, and so on back to index 0. The last parent is at index count / 2 - 1: every slot after it is a leaf, and a leaf has nothing below it to fix.
heapify 8 3 9 1 into an empty heap (count becomes 4, last parent = 4 / 2 - 1 = 1):
copied in heapify_down(1): heapify_down(0):
3 > 1, swap 8 > 1, swap, then 8 > 3, swap
8 8 1
/ \ / \ / \
3 9 1 9 3 9
/ / /
1 3 8
8 3 9 1 8 1 9 3 1 3 9 8Going bottom-up works because by the time you reach a parent, both of the small trees under it are already heaps.
Requirements:
1. When the new values do not all fit in the free room (count already used plus the new ones is more than capacity), return false and change nothing.
2. Otherwise copy every value onto the end of the heap's array, adding 1 to count for each.
3. Then call heapify_down for every index from count / 2 - 1 down to 0.
4. Return true. The heap may already hold values when the function is called.
Do NOT write a main function.
Expected Output:
heapify: yes [1, 4, 2, 9, 8, 7] count 6
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...