CJCoding With Joseph
15free / daySign inCreate account

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   4

Your 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.

Hints3 available
Topics:
Data Structures & AlgorithmsHeaps
1
Tab to indent (Esc then Tab to move on) · Ctrl+Enter to run · Shift+Alt+F to format · Ctrl+Space to expand shortcuts (p, fori)

Your Output

Run your code to see the output here...

Test Cases

Run your code to see test case results.