CJCoding With Joseph
15free / daySign inCreate account

Insert a Value and Report Whether It Fit

Complete min_heap_insert. It adds a value to the heap and returns true, or returns false when the heap has no room left. 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.

A new value always starts in the first free slot, which is index count. That keeps the tree complete, but the value may be smaller than its parent, so it has to bubble up: heapify_up swaps it with its parent again and again until the parent is no longer bigger.

insert 2 into this heap (count is 4, so the first free slot is index 4):

  step 1: place it         step 2: 2 < 6, swap        step 3: 2 < 3, swap

        3                        3                          2
       / \                      / \                        / \
      6   5                    2   5                      3   5
     / \                      / \                        / \
    9   2  <- new            9   6                      9   6

  3 6 5 9 2                3 2 5 9 6                  2 3 5 9 6

Your job is the bookkeeping around that climb: check for room, place the value, count it, then start the climb from the slot you used.

Requirements: 1. When count equals capacity, return false and change nothing. 2. Otherwise store the value at index count, add 1 to count, and call heapify_up on the slot the value went into. 3. Return true. 4. Leave heapify_up and the other provided functions as they are.

Do NOT write a main function.

Expected Output:

insert 8: yes [8]
insert 5: yes [5, 8]
insert 9: yes [5, 8, 9]
insert 2: yes [2, 5, 9, 8]

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