Least-cost merges with a heap (Huffman)

To merge files, or join ropes, at the least total cost when each merge costs the two sizes added together, always merge the two smallest that are left. A min-heap hands back the two smallest in O(log n) after every merge, so n items take O(n log n). The rule is the one David Huffman published in 1952 for codes with the least redundancy: with letter counts as the sizes, the merges build the code tree, and the total cost is the length of the coded text in bits. The problem is often called the minimum cost of ropes; here it is told with sorted log files.

Merging sorted log files

• [20, 4, 7, 9, 3] costs 87 at least: merge 3 and 4, then the two 7s, then 9 with 14 and last 20 with 23, for 7 + 14 + 23 + 43. Merging in the order given costs 138.
• [5, 5, 5, 5] costs 40: two pairs, then the two halves, for 10 + 10 + 20. Adding one file at a time to a growing file costs 45.
• [12] costs 0, because there is nothing to merge.

The brute force, and why it fails at these sizes

Try every pair at every step and keep the cheapest total. With k files left there are k(k − 1)/2 pairs to choose from, so n files have n!(n − 1)!/2ⁿ⁻¹ merge orders: 180 for the five files above, 2,571,912,000 for ten, and about 10^883,039 for 100,000.

# The brute force for merging files: at every step try every pair of the files that are left, merge it, and go on;
# keep the cheapest total. It is right by construction, and it counts the merge orders it tries.
from math import factorial, lgamma, log


def cheapest(sizes):
    """(the least total cost, the number of merge orders tried)"""
    if len(sizes) <= 1:
        return 0, 1
    best, orders = None, 0
    for i in range(len(sizes)):
        for j in range(i + 1, len(sizes)):
            rest = sizes[:i] + sizes[i + 1 : j] + sizes[j + 1 :] + [sizes[i] + sizes[j]]
            cost, tried = cheapest(rest)
            cost += sizes[i] + sizes[j]
            orders += tried
            best = cost if best is None else min(best, cost)
    return best, orders


def in_given_order(sizes):
    """Merge the first two files, then the result with the next file, and so on."""
    total, current = 0, sizes[0]
    for s in sizes[1:]:
        current += s
        total += current
    return total


for sizes in ([20, 4, 7, 9, 3], [5, 5, 5, 5], [12]):
    best, orders = cheapest(sizes)
    print(f"{sizes}: least cost {best} ({orders:,} merge order{'s' * (orders != 1)} tried); merged in the given order: {in_given_order(sizes)}")
for n in (10, 20):
    print(f"{n} files: {factorial(n) * factorial(n - 1) // 2 ** (n - 1):,} merge orders")  # C(n, 2) * C(n-1, 2) * ... * 1
n = 100_000
digits = (lgamma(n + 1) + lgamma(n) - (n - 1) * log(2)) / log(10)
print(f"{n:,} files: about 10^{digits:,.0f} merge orders")

[20, 4, 7, 9, 3]: least cost 87 (180 merge orders tried); merged in the given order: 138
[5, 5, 5, 5]: least cost 40 (18 merge orders tried); merged in the given order: 45
[12]: least cost 0 (1 merge order tried); merged in the given order: 0
10 files: 2,571,912,000 merge orders
20 files: 564,480,989,588,730,591,336,960,000,000 merge orders
100,000 files: about 10^883,039 merge orders

What to notice

• Every merge copies its two files once more. A file is paid for once for every merge above it in the tree, so the total is each size times the number of merges it goes through.
• So small files belong deep and large files high. Merging the two smallest first sends them through the most merges, and the largest file joins last, through one.
• The merged file joins the others. After every merge the two smallest have to be found again, among the files left and the new one.

A min-heap finds them in O(log n), for O(n log n) in all. When the sizes arrive sorted, two queues give the same total in O(n). Huffman codes come from the same merges, with letter counts as the sizes.

The heap, step by step Pro: opens with a Pro, Premium or Ultimate pass