Greedy Choice
Always merge the two smallest values first. This minimizes the total cost because smaller values get added to the cost more times (they're merged earlier and their cost propagates up).
Algorithm
minHeap = all values
totalCost = 0
while heap.size > 1:
a = extractMin(), b = extractMin()
cost = a + b
totalCost += cost
insert(cost)
totalCost = 0
while heap.size > 1:
a = extractMin(), b = extractMin()
cost = a + b
totalCost += cost
insert(cost)
Interactive Visualization
Picking Merged Result Final
Min Heap (sorted view)
Merge History
—
Step 0 of 0
Merging
—
Step Cost
0
Total Cost
0
Heap Size
0
Ready. Press Play or Next to start.
✓ Done
Speed
C++ — Minimum Merge Cost
int minCostMerge(vector<int>& arr) { priority_queue<int, vector<int>, greater<int>> pq; for (int x : arr) pq.push(x); int totalCost = 0; while (pq.size() > 1) { int a = pq.top(); pq.pop(); int b = pq.top(); pq.pop(); int cost = a + b; totalCost += cost; pq.push(cost); } return totalCost; }
Complexity
Time
O(N log N)
N-1 merges, each with O(log N) heap ops.
Space
O(N)
Min heap stores all elements.