Check Whether Two Heaps Hold the Same Values
Check Whether Two Heaps Hold the Same Values
Write min_heap_same_values. It returns true when two heaps hold exactly the same values (the same numbers, the same number of times each), and false otherwise. Neither heap may be 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.
Comparing the two arrays slot by slot does NOT work. The same values can be arranged as a heap in more than one way, depending on the order they were inserted in.
two different arrays, the same values:
1 1
/ \ / \
2 3 3 2
1 2 3 1 3 2 slot 1 differs, but both hold 1, 2 and 3
what does match: the order the values come OUT in
remove, remove, remove -> 1 2 3 1 2 3So compare what comes out. Take a copy of each heap, then remove from both copies together, one value from each, and compare the pair. A different pair means the answer is false. Destroy both copies before you return, whatever the answer is.
Requirements:
1. When the two counts differ, return false (no copies needed).
2. Otherwise copy both heaps with min_heap_copy, and remove from the two copies in step, comparing each pair of removed values.
3. Return true only when every pair matched.
4. Destroy both copies on every path. Do not change first or second.
Do NOT write a main function.
Expected Output:
same values: yes first afterwards: [1, 2, 3, 4, 5] second afterwards: [1, 4, 2, 5, 9]
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...