Optimal File Merge Using Min Heap in Java

1. Introduction

The Optimal File Merge problem asks us to merge multiple files into a single file with the minimum possible total computation cost.

Each file has a certain size. When two files are merged, the cost of the operation is the sum of their sizes.

For example, if we merge files of sizes 3 and 2:

Cost = 3 + 2 = 5
New file size = 5

The newly created file can then be merged with another file.

The important question is:

In which order should we merge the files so that the total cost is minimum?

The answer is to always merge the two smallest files first.

To efficiently find the two smallest files, we use a Min Heap, implemented in Java using PriorityQueue.

2. Example

Consider:

files = [3, 2, 4]

There are multiple ways to merge these files.

Approach 1

2 + 3 = 5
5 + 4 = 9

Total cost = 5 + 9 = 14

Approach 2

3 + 4 = 7
7 + 2 = 9

Total cost = 7 + 9 = 16

Therefore:

Minimum Cost = 14

The first approach is better.

3. Important Observation

The main observation is:

Always merge the two smallest files first.

Why?

Suppose we merge a large file early.

That merged file becomes part of future merge operations, so its size contributes to the cost multiple times.

By merging smaller files first, we keep the intermediate file sizes as small as possible.

This is a Greedy Algorithm.

4. Why Do We Need a Min Heap?

At every step, we need to find:

Smallest file
Second smallest file

If we search the array every time, it can become inefficient.

For example, if there are n files and we repeatedly search for the smallest elements, the complexity can become large.

A Min Heap solves this efficiently.

In Java:

PriorityQueue<Integer> pq = new PriorityQueue<>();

By default, Java's PriorityQueue works as a Min Heap.

Therefore:

pq.poll()

always returns the smallest element.

5. Algorithm

The algorithm is simple:

Step 1

Create a Min Heap.

Step 2

Insert all file sizes into the heap.

Step 3

While there is more than one file:

Remove the smallest file.
Remove the second smallest file.
Add their sizes.
Add the merged size to the total cost.
Insert the merged file back into the heap.

Step 4

Return the total cost.

6. Java Code

import java.util.PriorityQueue;

class Solution {
    public int minComputation(int[] files) {

        // Create a Min Heap
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // Add all file sizes to the heap
        for (int file : files) {
            pq.add(file);
        }

        int totalCost = 0;

        // Continue until only one file remains
        while (pq.size() > 1) {

            // Get the two smallest files
            int x = pq.poll();
            int y = pq.poll();

            // Merge the two files
            int merged = x + y;

            // Add merge cost
            totalCost += merged;

            // Add the merged file back to the heap
            pq.add(merged);
        }

        return totalCost;
    }
}

7. Code Explanation

Let's understand each part of the code.

Creating the Min Heap

PriorityQueue<Integer> pq = new PriorityQueue<>();

Java's PriorityQueue automatically keeps the smallest element at the top.

For example:

Input:
[3, 2, 4]

Min Heap:
2
3
4

So:

pq.poll();

returns:

Adding Files

for (int file : files) {
    pq.add(file);
}

Every file size is inserted into the priority queue.

For:

files = [2, 3, 6, 5, 7, 4]

The heap contains all six values.

The important point is that we don't need to manually sort the array.

Loop Condition

while (pq.size() > 1)

We continue merging as long as there are at least two files.

When only one file remains, all files have been merged.

Getting the Two Smallest Files

int x = pq.poll();
int y = pq.poll();

Because pq is a Min Heap:

x = smallest
y = second smallest

For example:

Heap = [2, 3, 4, 5, 6, 7]

x = 2
y = 3

Merging

int merged = x + y;

If:

x = 2
y = 3

then:

merged = 5

The merge operation costs 5.

Adding to Total Cost

totalCost += merged;

The cost of each merge is added to the answer.

For example:

First merge = 5
Second merge = 9
Third merge = 11
...

The final answer is the sum of all these merge costs.

Adding the Merged File Back

pq.add(merged);

This step is very important.

After merging:

2 + 3 = 5

we now have a new file of size 5.

That file must be available for future merging.

Therefore, we put it back into the heap.

8. Complete Dry Run

Let's take:

files = [2, 3, 6, 5, 7, 4]

Initially:

[2, 3, 4, 5, 6, 7]

Step 1

Take two smallest:

2 + 3 = 5

Cost:

Heap becomes:

[4, 5, 5, 6, 7]

Step 2

Take two smallest:

4 + 5 = 9

Cost:

Total:

5 + 9 = 14

Heap:

[5, 6, 7, 9]

Step 3

Take:

5 + 6 = 11

Cost:

Total:

14 + 11 = 25

Heap:

[7, 9, 11]

Step 4

Take:

7 + 9 = 16

Cost:

Total:

25 + 16 = 41

Heap:

[11, 16]

Step 5

Take:

11 + 16 = 27

Cost:

Total:

41 + 27 = 68

Now only one file remains.

Therefore:

Answer = 68

9. Why Is This a Greedy Algorithm?

A Greedy Algorithm makes the best possible choice at the current step.

Here, our choice is:

Choose the two smallest files.

We don't try every possible merging order.

Instead, we make the locally optimal choice at every step.

For this problem, this greedy strategy produces the globally optimal result.

This is the same basic idea used in:

Huffman Coding
Connect Ropes
Minimum Cost of Connecting Ropes
Optimal Merge Pattern

10. Edge Cases

Case 1: Only One File

files = [10]

There is nothing to merge.

So:

Answer = 0

The code handles this automatically because:

while (pq.size() > 1)

is false.

Case 2: Two Files

files = [5, 7]

Only one merge is required:

5 + 7 = 12

Answer:

Case 3: Equal File Sizes

files = [5, 5, 5, 5]

The algorithm still works correctly:

5 + 5 = 10
5 + 5 = 10
10 + 10 = 20

Total:

10 + 10 + 20 = 40

11. Time Complexity

There are n files.

Each file is inserted into the priority queue.

Each merge performs:

poll()
poll()
add()

Each PriorityQueue operation takes:

O(log n)

There are approximately n - 1 merges.

Therefore:

Time Complexity = O(n log n)

12. Space Complexity

The PriorityQueue can contain up to n elements.

Therefore:

Space Complexity = O(n)

13. Important Interview Pattern

Whenever you see a problem like:

"Repeatedly combine two elements and minimize the total cost."

Think immediately:

Min Heap
   ↓
Take two smallest
   ↓
Combine them
   ↓
Add cost
   ↓
Put result back
   ↓
Repeat

This is one of the most important Greedy + Heap patterns for coding interviews.

14. Final Takeaway

The key idea behind Optimal File Merge is very simple:

Always merge the two smallest files first.

A Java PriorityQueue gives us an efficient way to find those two smallest files.

The complete pattern is:

PriorityQueue<Integer> pq = new PriorityQueue<>();

for (int file : files) {
    pq.add(file);
}

int totalCost = 0;

while (pq.size() > 1) {

    int first = pq.poll();
    int second = pq.poll();

    int merged = first + second;

    totalCost += merged;

    pq.add(merged);
}

return totalCost;

Remember this formula:

Minimum Merge Cost = Repeatedly merge the two smallest elements using a Min Heap.

Time: O(n log n)
Space: O(n)