CJCoding With Joseph
15free / daySign inCreate account

Make an Independent Copy of a Heap

Write min_heap_copy. It returns a brand new heap that holds the same values as source, in the same slots, with the same capacity. Changing one heap afterwards must not change the other.

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 trap is the values pointer. If the new struct simply copies that pointer, both heaps share ONE array: a change through either heap shows up in both, and destroying both frees the same array twice. A real copy needs its own array, with the numbers copied across one by one.

wrong: the pointer is copied (one array, shared)

  source: capacity 4, count 3, values ---+
                                         +--> | 2 | 7 | 5 | ? |
  copy:   capacity 4, count 3, values ---+

right: the numbers are copied (two arrays)

  source: capacity 4, count 3, values ------> | 2 | 7 | 5 | ? |

  copy:   capacity 4, count 3, values ------> | 2 | 7 | 5 | ? |

min_heap_initialize already makes a struct with its own array, so it does half the job for you.

Requirements: 1. Make the new heap with min_heap_initialize, with the same capacity as source. 2. Copy the values in slots 0 to count - 1 into the same slots of the new heap. 3. Set the new heap's count to match. 4. Return the new heap. Do not change source.

Do NOT write a main function.

Expected Output:

original: [2, 7, 5, 9]
copy:     [2, 7, 5, 9]
copy capacity 6, count 4
shares the array: no
after changing the copy:
original: [2, 7, 5, 9]
copy:     [1, 7, 5, 9]

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