CJCoding With Joseph
15free / daySign inCreate account

Remove the Root and Hand It Back Through a Pointer

Complete min_heap_remove. It takes the smallest value out of the heap, hands it back through the pointer value, and returns true. On an empty heap it returns false. 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.

The smallest value is the root, but you cannot just delete slot 0: that would leave a hole at the top of the tree. Instead the LAST value moves into the root (which keeps the tree complete), and then it sinks: heapify_down swaps it with its smaller child until neither child is smaller.

remove from this heap (count is 5):

  before               last value to the root    4 sinks: smaller child is 2

        1                      4                        2
       / \                    / \                      / \
      3   2                  3   2                    3   4
     / \                    /                        /
    7   4                  7                        7

  1 3 2 7 4              4 3 2 7                  2 3 4 7

  *value becomes 1, count becomes 4

Requirements: 1. When the heap is empty, return false and leave *value alone. 2. Otherwise copy the root into *value. 3. Subtract 1 from count, move the value from the old last slot into index 0, and call heapify_down on index 0. 4. Return true.

Do NOT write a main function.

Expected Output:

removed 1
[2, 3, 4, 7]
removed 2
[3, 7, 4]

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