from collections import namedtuple
from heapq import heapify, heappop, heappush

Node = namedtuple("Node", ["value", "name", "left", "right"])


def encode(freq: dict[str, float]) -> dict[str, str]:
    # convert everything into the node
    nodes = [Node(v, k, None, None) for k, v in freq.items()]
    heapify(nodes)

    while len(nodes) > 1:
        a = heappop(nodes)
        b = heappop(nodes)
        combined = Node(a.value + b.value, "", a, b)
        heappush(nodes, combined)

    root = nodes[0]

    # iterate the node
    def iterate(node, prefix=""):
        if node.left is None:
            yield (node.name, prefix)
        else:
            yield from iterate(node.left, prefix + "1")
            yield from iterate(node.right, prefix + "0")

    return dict(iterate(root))


if __name__ == "__main__":
    assert (encode(dict(a=0.4, b=0.35, c=0.2, d=0.05))) == dict(
        a="1", b="00", c="010", d="011"
    )