Optimal Merge Pattern

When merging two files of sizes a and b costs a+b and creates a file of that size, the order of merges controls total work. The optimal merge pattern repeatedly merges the two smallest available sizes. A min-heap implements this efficiently. The proof comes from viewing the merge history as a binary tree, revealing the same structure used by Huffman coding.

Prerequisites: Priority Queues; binary trees; structural induction.

Build the idea

1. Express cost using a tree

   Each original size is a leaf weight. Every merge is an internal node whose weight is the sum of its descendant leaves. A leaf contributes its weight once for every ancestor merge, so total merge cost is the sum of leaf weight times depth. Zero or one file requires no merge and has cost zero under this merge-work model.

2. Choose the two smallest

   Put every size in a min-heap. Remove its smallest two values a,b, pay a+b and insert their sum. Continue until one combined file remains. Do not merge the smallest with the largest or sort only once and ignore newly created files: merged weights must re-enter the candidate pool.

   $$\mathrm{mergeCost}=\Sigma \mathrm{leafWeight}·\mathrm{leafDepth}$$

3. Correctness proof: sibling exchange and contraction

   A full binary merge tree has a deepest sibling pair of leaves. Move the two smallest weights to those deepest positions by swapping with their occupants. For weights x≤y and depths deep≥shallow, assigning x deeper changes cost by (x−y)(deep−shallow)≤0. Thus some optimal tree has the two smallest as siblings. Contract their parent into a leaf of weight a+b: remaining cost is an optimal smaller instance plus a+b. Induction proves repeated smallest-pair merging optimal.

4. Trace the sample

   Sizes [10,20,30,40] first merge 10 and 20, paying 30. The heap becomes [30,30,40]; merge the two 30s, paying 60. Finally merge 40 and 60, paying 100. Total is 190, not just the final size 100, because material can be processed multiple times at different depths.

   Merge	New group	Cumulative cost
   10+20	30	30
   30+30	60	90
   40+60	100	190

5. Distinguish related problems

   This model allows any two groups to merge. If only adjacent files in a fixed order may merge, the sibling exchange can violate the order constraint and interval DP may be needed. Huffman coding uses the same weighted tree objective but also labels left/right edges to produce prefix-free codes. This lesson outputs cost only; the coding lesson explicitly builds the tree.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<queue>
#include<vector>
#include<functional>
int main(){
    int n;
    std::cin>>n;
    std::priority_queue<long long,std::vector<long long>,std::greater<long long>>heap;
    for(int i=0;i<n;++i){
        long long x;
        std::cin>>x;
        heap.push(x);
    }
    long long total=0;
    while(heap.size()>1){
        long long a=heap.top();
        heap.pop();
        long long b=heap.top();
        heap.pop();
        long long sum=a+b;
        total+=sum;
        heap.push(sum);
    } // Merge the two lightest subtrees.
    std::cout<<total<<'\n';
}

Complexity analysis

O(n log n) time with heap insertion and n−1 merges, O(n) heap storage. Total initial size≤10^11 and any leaf depth≤n−1, so even the conservative cost bound below 10^16 fits long long.

Example input and output

Read n (0..100000), then n nonnegative file sizes at most 10^6. Any two files may merge at cost equal to their combined size. Print minimum total merge cost.

Input

4
10 20 30 40

Output

190

The paid merge sizes are 30,60,100; their sum is 190.

Practical applications

Use for minimum unrestricted merge work, consolidation and the cost component of Huffman coding. If merge cost depends on more than the sum or choices are restricted to neighbors, re-derive the proof instead of reusing the heap rule.

Check your understanding

Why must a merged size be inserted into the heap again?

Put it into practice

Enumerate all merge pairs recursively for up to six files.