Insert a Value and Report Where It Lands
Insert a Value and Report Where It Lands
Complete heap_insert_at(heap, value). It inserts value into the min heap and returns the index where the value finally ends up, or -1 when the heap is already full. There is no heapify_up in this file, so the bubble up loop goes right inside the function.
Reminder: how an insert works. 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. To insert, put the new value in the first free slot, index heap->size, so the tree stays complete. Then bubble it up (heapify up): while it is smaller than its parent at (i - 1) / 2, swap the two and carry on from the parent's slot.
step 1: put 3 in the first free slot, index 7
2
/ \
5 4
/ \ / \
9 7 8 6
/
[3] 3 is at index 7, its parent (index 3) holds 9
step 2: 3 < 9, so swap them
2
/ \
5 4
/ \ / \
[3] 7 8 6 3 is at index 3, its parent (index 1) holds 5
/
9
step 3: 3 < 5, so swap them
2
/ \
[3] 4 3 is at index 1, its parent (index 0) holds 2
/ \ / \
5 7 8 6
/
9
step 4: 3 is not smaller than 2, so it stops at index 1 and the function returns 1
index: 0 1 2 3 4 5 6 7
before: 2 5 4 9 7 8 6
after: 2 3 4 5 7 8 6 9Keep the moving value's index in a variable. After every swap the value sits in its parent's old slot, so the index becomes the parent index. When the loop ends, that variable is exactly the number to return: here the 3 went in at index 7 and ended at index 1.
Requirements:
1. When the heap is full (heap_is_full), return -1 and change nothing.
2. Otherwise store value at index heap->size and add 1 to heap->size.
3. While the value is not at the root and is smaller than its parent, swap it with its parent and move up. A value equal to its parent stays where it is.
4. Return the index where the value stopped: 0 when it climbs to the root, heap->size - 1 when it never moves.
5. Leave the struct, heap_init, heap_load, get_parent_index, swap, heap_is_full and heap_print as they are.
Do NOT write a main function.
Expected Output:
MinHeap: 3 6 4 9 8 7 insert 10: index 6 MinHeap: 3 6 4 9 8 7 10 insert 7: index 3 MinHeap: 3 6 4 7 8 7 10 9 insert 1: index 0 MinHeap: 1 3 4 6 8 7 10 9 7
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...