Insert Into a Heap That Grows When It Is Full
Insert Into a Heap That Grows When It Is Full
The lab's min_heap_insert refuses a value when the heap is full. Write min_heap_insert_grow, which never refuses: when the heap is full it makes the array bigger first, then inserts as usual. heapify_up 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.
An array from malloc cannot be stretched in place, but realloc does the next best thing: it gives you a bigger block that already holds the old values (it may be the same block, or a new one with the values copied over) and frees the old one for you. It returns the address of the block to use from now on, so that address must be stored back into values. Doubling the capacity each time means growing happens rarely.
insert 1 into a full heap (capacity 3, count 3):
before values --> | 2 | 5 | 4 | capacity 3
realloc values --> | 2 | 5 | 4 | ? | ? | ? | capacity 6
then insert values --> | 1 | 2 | 4 | 5 | ? | ? | count 4
2 1
/ \ / \
5 4 -> 2 4
/
5realloc returns NULL when it cannot get the memory, and in that case the old block is still valid. So keep its answer in a separate pointer and check it before you overwrite values.
Requirements:
1. When the heap is full, the new capacity is double the old one, or 1 when the old capacity was 0.
2. Call realloc for that many ints. When it returns NULL, return false and change nothing.
3. Otherwise store the new address in values and the new size in capacity.
4. Then insert as usual: store the value at index count, add 1 to count, call heapify_up on that slot, and return true.
Do NOT write a main function.
Expected Output:
insert 5: capacity 2 [5] insert 3: capacity 2 [3, 5] insert 8: capacity 4 [3, 5, 8] insert 1: capacity 4 [1, 3, 8, 5] insert 9: capacity 8 [1, 3, 8, 5, 9]
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...