Optimal File Merge

Problem Overview

Merging two files of sizes x and y costs x plus y, and the combined file can be merged again.

Intuition

Merging two files of sizes x and y costs x plus y, and the combined file can be merged again. Each later merge pays that size once more, so a file chosen early is paid the most times. Every step should therefore join the two smallest sizes still available. A binary heap keeps the sizes and returns those two in logarithmic time. Their sum is added to the total and pushed back as a new file. One file, or none, needs no merge and costs 0. The heap stores plain numbers rather than boxed integers.

Algorithm

1Return 0 when fewer than two files are present.
2Copy the sizes into a binary heap and heapify them.
3While at least two files remain, remove the two smallest, add their sum to the cost, and push that sum back.
4Return the accumulated cost.

Example Walkthrough

Input: files = [2, 3, 4]

1. The two smallest are 2 and 3. Merging them costs 5, and the files are now 4 and 5.
2. Merging 4 and 5 costs 9.
3. The total is 5 plus 9, which is 14.

Output: 14

Common Pitfalls

• Merging the two largest first leaves the small files inside every later sum, so they are paid again and again.
• The order of the input does not matter. Only the multiset of sizes does.
• The merged size has to be pushed back. Forgetting that reinsertion drops the file from every later step.
• Two large sizes can overflow a 32 bit sum before the total does. Keep the heap values in 64 bit integers.

Optimal File Merge.java

Java

// Approach: A merged file is paid for again every time it is merged later, so
// the cheapest sequence always joins the two smallest sizes first. A binary
// heap stores the sizes as plain longs and returns those two in logarithmic
// time. Their sum is both the cost of this step and the size pushed back.
// Complexity: O(n log n) time, O(n) extra space.
class Solution {
    public int minComputation(int[] files) {
        int n = files.length;
        if (n <= 1)
            return 0;

        long[] heap = new long[n];
        for (int i = 0; i < n; i++)
            heap[i] = files[i];
        for (int i = n / 2 - 1; i >= 0; i--)
            siftDown(heap, n, i);

        long cost = 0;
        int size = n;
        while (size > 1) {
            long a = poll(heap, size);
            size--;
            long b = poll(heap, size);
            size--;
            long sum = a + b;
            cost += sum;
            heap[size] = sum;
            siftUp(heap, size);
            size++;
        }
        return (int) cost;
    }

    private static long poll(long[] heap, int size) {
        long top = heap[0];
        int last = size - 1;
        if (last > 0) {
            heap[0] = heap[last];
            siftDown(heap, last, 0);
        }
        return top;
    }

    private static void siftUp(long[] heap, int i) {
        long value = heap[i];
        while (i > 0) {
            int parent = (i - 1) >> 1;
            if (heap[parent] <= value)
                break;
            heap[i] = heap[parent];
            i = parent;
        }
        heap[i] = value;
    }

    private static void siftDown(long[] heap, int size, int i) {
        long value = heap[i];
        while (true) {
            int left = i * 2 + 1;
            if (left >= size)
                break;
            int right = left + 1;
            int small = right < size && heap[right] < heap[left] ? right : left;
            if (value <= heap[small])
                break;
            heap[i] = heap[small];
            i = small;
        }
        heap[i] = value;
    }
}

Was this solution helpful?