Cheapest merging (Huffman-style)

Many problems repeatedly merge two items into one where the cost of a merge is the sum of their sizes: connecting ropes or sticks, merging sorted files into one, building a Huffman code. The total cost depends heavily on the order.

Every original item's size is paid once for each merge it takes part in, so big items should be merged as few times as possible, meaning as late as possible. The greedy rule is: always merge the two currently smallest items. A min-heap makes each step O(log n).

Huffman coding is the famous application: symbols are items, their frequencies are sizes, and the merge tree becomes a prefix code. Frequent symbols end up near the root with short codes, rare ones deep with long codes, and the total encoded length is minimised among all prefix codes.

1. 1Put all sizes in a min-heap: O(n) with heapify.
2. 2While more than one item remains, pop the two smallest a and b, add a + b to the total cost, and push a + b back.
3. 3After n - 1 merges one item is left; the accumulated total is the answer.
4. 4Why it works: the total cost equals the sum over items of size x depth in the merge tree. In some optimal tree the two smallest items can be swapped into the deepest pair of siblings without increasing the cost (an exchange argument), so merging them first is safe, and the rest is the same problem with one fewer item.
5. 5For Huffman coding, also record each merge as a parent node; reading left = 0 and right = 1 from the root gives each symbol's code.

import heapq


def min_cost_connect(sticks):
    """Join all sticks; joining lengths a and b costs a + b."""
    heap = list(sticks)
    heapq.heapify(heap)
    total = 0
    while len(heap) > 1:
        a = heapq.heappop(heap)    # two smallest
        b = heapq.heappop(heap)
        total += a + b
        heapq.heappush(heap, a + b)
    return total

# min_cost_connect([4, 3, 2, 6]) -> 29
# Huffman: with frequencies [5, 9, 12, 13, 16, 45] the same loop
# returns 224, the total number of bits in the encoded text.

heapify is O(n), then n - 1 rounds of two pops and one push, each O(log n), for O(n log n) total time and O(n) space.

Cost: O(n log n) time with a binary heap and O(n) space; with already sorted input, a two-queue method runs in O(n).