CJCoding With Joseph
15free / daySign inCreate account

Merge Two Heaps Into a New One

Write min_heap_merge. It returns a new heap that holds every value of two other heaps. The two heaps it is given are not changed.

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 cannot just place one array after the other: the result would usually break the heap rule, because a small value from the second heap would end up as a leaf. The combined values have to be made into a heap again. min_heap_heapify does exactly that for a plain array of ints, and a heap's values field IS a plain array of ints.

first:  2 6 3          second:  1 5

      2                      1
     / \                    /
    6   3                  5

side by side would be  2 6 3 1 5 : not a heap (1 is under 6)

merged and repaired:

          1
        /   \
       2     3            every value from both, smallest at the root
      / \
     6   5

The new heap gets room for both: its capacity is the two capacities added together.

Requirements: 1. Make a new heap whose capacity is first->capacity + second->capacity. 2. Add every value of first and every value of second to it, so it ends as a valid min heap. 3. Return the new heap. Do not change first or second.

The tests check the new heap's count and capacity, that it is a valid heap, and the order its values come out in. They do not depend on the exact slot each value lands in.

Do NOT write a main function.

Expected Output:

count 5 of capacity 7
valid heap: yes
smallest first: 1 2 3 5 6
first afterwards: [2, 6, 3]
second afterwards: [1, 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.