class Node:
    def __init__(self,data,internal=False):
        self.data = data  #frequecny of a char
        self.internal = internal
        self.visited = False
        self.left = None
        self.right = None

        self.prefix =""


class HuffmanTree:
    def __init__(self,root=None):
        self.root = root

    def insert(self,data_list):
        #creating all leaf nodes and storing as node_list
        node_list = []
        x = 0
        for i in data_list:
            node_list.insert(x,Node(data_list[x]))
            x = x+1
        #creating huffman tree
        while True:

            if(len(node_list)>1):

                s1 = node_list[0].data
                s2 = node_list[1].data
                s = s1+s2

                #creating internal node
                IN = Node(s,internal=True)
                IN.left = node_list[0]
                IN.right = node_list[1]

                ##deleting used leafs/nodes
                #deleting from list from head
                if len(node_list)>=2:
                    del node_list[0]
                    del node_list[0]
                else:
                    del node_list[0]

                #inserting new internal node (IN)
                node_list.insert(0,IN)
                sort_nodes(node_list)
            else:
                self.root = node_list[0]
                break

def sort_nodes(A):
    #selection sort algorithm
    for i in range(len(A)):

        # Find the minimum element in remaining
        # unsorted array
        min_idx = i
        for j in range(i+1, len(A)):
            if A[min_idx].data > A[j].data:
                min_idx = j

        A[i], A[min_idx] = A[min_idx], A[i]
    return A

def printCode(node,prefix):
    if node.left:
        node.prefix = node.prefix+"0"
        printCode(node.left,node.prefix)

    if node.right:
        node.prefix = node.prefix+"1"
        printCode(node.right,node.prefix)

    if node.internal ==False:
        print(node.data,node.prefix)


b = [9,5,12,13,16,45]
b.sort()
c = HuffmanTree()
c.insert(b)
printCode(c.root,"")