CJCoding With Joseph
15free / daySign inCreate account

Join Ropes for the Smallest Total Cost

Write min_join_cost. You are given the lengths of some ropes. Joining two ropes costs the SUM of their lengths and leaves one longer rope. Keep joining until one rope is left, and return the smallest total cost that is possible.

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 order of joining matters, because a rope that is joined early gets paid for again in every later join it is part of. So long ropes should be joined as late as possible. That gives a simple rule: always join the two SHORTEST ropes there are right now. A min heap is the perfect tool, because the joined rope goes back into the pile and may or may not be among the shortest next time.

ropes: 4 3 2 6

  heap holds 2 3 4 6     remove 2 and 3     cost 5       insert 5
  heap holds 4 5 6       remove 4 and 5     cost 9       insert 9
  heap holds 6 9         remove 6 and 9     cost 15      insert 15
  heap holds 15          one rope left: stop

  total cost: 5 + 9 + 15 = 29

  joining them left to right instead (4+3, then +2, then +6) costs 7 + 9 + 15 = 31

The heap functions you need are already written: min_heap_initialize, min_heap_heapify, min_heap_remove, min_heap_insert and min_heap_destroy.

Requirements: 1. Put all the lengths in a heap with room for count values. 2. While the heap holds more than one value: remove the two smallest, add their sum to the total cost, and insert their sum. 3. Destroy the heap and return the total cost. 4. One rope, or no ropes, costs 0.

Do NOT write a main function.

Expected Output:

smallest cost: 29

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