Total frequency of all leaves below it. An exchange argument allows the two least frequent symbols to be deepest siblings, reducing to a smaller problem.

Every time two subtrees merge, all their symbols move one level deeper. Their combined frequency is exactly the extra cost paid, so merge the cheapest pair.

What the function promises: Return minimum weighted code length for nonnegative frequencies. Zero-frequency symbols are ignored; zero or one positive symbol costs zero bits under this model.

from heapq import heapify, heappop, heappush

def huffman_cost(frequencies):
    heap = [value for value in frequencies if value > 0]
    heapify(heap)
    total = 0
    while len(heap) > 1:
        merged = heappop(heap) + heappop(heap)
        total += merged
        heappush(heap, merged)
    return total

assert huffman_cost([5,9,12,13,16,45]) == 224
assert huffman_cost([10]) == 0

Work and storage: O(s log s) time and O(s) space for s positive-frequency symbols.

When to recognize it: An exchange argument allows the two least frequent symbols to be deepest siblings, reducing to a smaller problem.

Check before applying it: Changing to unequal edge costs or adaptive unknown frequencies changes the proof.

Build tree nodes during merging, derive code lengths, then assign canonical codes in length-and-symbol order.