Insert a Value Into a Min Heap
Insert a Value Into a Min Heap
Complete heap_insert. It adds one value to the heap and returns 1, or returns 0 and changes nothing when the heap is already full. The bubbling up is done for you by the provided heapify_up.
Reminder: insert is two moves. A min heap is a complete binary tree kept in an array, filled row by row, left to right, with no gaps, and every parent is smaller than or equal to its children, so the smallest value is at index 0. The first empty slot is always data[size], so the new value goes there and size grows by one. The tree is still complete, but the new value may be smaller than its parent, and heapify_up fixes that by swapping it upward until its parent is not bigger.
Here 1 is inserted into the heap 2 5 4 8 7:
Before: size 5, so the first empty slot is index 5.
2
/ \
5 4
/ \
8 7
Move 1: data[5] = 1, then size becomes 6.
2
/ \
5 4
/ \ /
8 7 1 1 is new, at index 5
Move 2: heapify_up(heap, 5) takes over.
1 < 4, so swap index 5 with index 2.
2
/ \
5 1 1 moved up to index 2
/ \ /
8 7 4
1 < 2, so swap index 2 with index 0. Index 0 is the root: stop.
1 1 climbed to the root
/ \
5 2
/ \ /
8 7 4
index: 0 1 2 3 4 5
value: 1 5 2 8 7 4Your function does move 1 itself and hands move 2 to heapify_up. The index to pass is the slot the value was placed in, which is size - 1 once size has grown.
Requirements:
1. When heap_is_full(heap) is true (15 values, HEAP_CAPACITY), return 0 and change nothing: not data, not size.
2. Otherwise store value in heap->data[heap->size], add one to heap->size, then call heapify_up on the index of the new value.
3. Return 1 after the value is added.
4. Duplicates are allowed: inserting a value that is already in the heap adds a second copy.
5. Leave the MinHeap struct and the provided functions (heap_init, get_parent_index, swap, heap_is_full, heapify_up, heap_print) as they are.
Do NOT write a main function.
Expected Output:
MinHeap: insert 7: added MinHeap: 7 insert 3: added MinHeap: 3 7 insert 9: added MinHeap: 3 7 9 insert 1: added MinHeap: 1 3 9 7 insert 5: added MinHeap: 1 3 9 7 5
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...