CJCoding With Joseph
15free / daySign inCreate account

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 3

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

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.