import heapq

freq = {"A":1, "B":3, "C":7, "D":2}

class Node:
    def __init__(self, symbol, freq):
        self.symbol = symbol
        self.freq = freq
        self.left = None
        self.right = None
        
    def __lt__(self, other):
        # Ikke n?dvendig
        if self.symbol != None:
            return False
        return True
    
        # Kan ogs? bruke denne:
        return self.freq < other.freq

PQ = []
for symbol in freq:
    n = Node(symbol, freq[symbol])
    heapq.heappush(PQ, (freq[symbol], n))

while len(PQ) >= 2:
    a = heapq.heappop(PQ)[1]
    b = heapq.heappop(PQ)[1]
    ny = Node(None, a.freq + b.freq)

    ny.right = a
    ny.left = b

    heapq.heappush(PQ, (ny.freq, ny))

root = PQ[0][1]
res = {}

def find_code(node, current_code):
    if node.symbol != None:
        res[node.symbol] = current_code
        return 
    find_code(node.left, current_code + "1")
    find_code(node.right, current_code + "0")

find_code(root, "")

print(res)