CJCoding With Joseph
15free / daySign inCreate account

Replace the Root Without Changing the Count

Complete min_heap_replace. It takes the smallest value out and puts a new value in, in one step. The old smallest value comes back through the pointer value. heapify_down 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.

You could do this with a remove followed by an insert, but that walks the tree twice: once down, once up. Replace is cheaper. The new value is written straight over the root, and one trip down puts it where it belongs. The number of values never changes.

replace the smallest with 8:

  before            8 written over the root     8 sinks past 3, then past 5

        1                    8                          3
       / \                  / \                        / \
      3   4                3   4                      5   4
     / \                  / \                        / \
    5   9                5   9                      8   9

  1 3 4 5 9            8 3 4 5 9                  3 5 4 8 9

  *value becomes 1, count stays 5

Requirements: 1. When the heap is empty, return false and change nothing. 2. Otherwise copy the root into *value, write replacement into index 0, and call heapify_down on index 0. 3. Return true. count must not change.

Do NOT write a main function.

Expected Output:

took out 1
[2, 4, 6, 7, 5]
took out 2
[0, 4, 6, 7, 5]
count 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.