CJCoding With Joseph
15free / daySign inCreate account

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
                            /
                           5

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

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