Join Ropes for the Smallest Total Cost
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 = 31The 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.
Your Output
Run your code to see the output here...