1. from collections import defaultdict
2. class Node:
3.     def __init__(self,val, char=None):
4.         self.val=val
5.         self.left=None
6.         self.right=None
7.         self.code=""
8.         self.char=char
9.  
10. def bubbleSort(table):
11.     for i in range (len(table)-1):
12.         for j in range (i+1, len(table)):
13.             if(table[i].val>table[j].val):
14.                 t = table[i]
15.                 table[i]=table[j]
16.                 table[j]=t
17.  
18. def createTable(charFreq):
19.     table=[]
20.     for key in charFreq:
21.         table.append(Node(charFreq[key], key))
22.     return table
23.        
24. def createHeap(charFreq):
25.     table=createTable(charFreq)
26.     while len(table)>1:
27.         bubbleSort(table)
28.         n1,n2=table.pop(0),table.pop(0)
29.         node = Node(n1.val+n2.val)
30.         node.left, node.right=n1, n2
31.         table.append(node)
32.  
33.     return node #this will be the root node
34.  
35. leafNodes=[]
36. def generateCodes(rootNode):
37.     global leafNodes
38.     if rootNode.left and rootNode.right:
39.         rootNode.left.code=rootNode.code+"0"
40.         rootNode.right.code=rootNode.code+"1"
41.         generateCodes(rootNode.left)
42.         generateCodes(rootNode.right)
43.     else:
44.         leafNodes.append(rootNode)
45.    
46. print("Enter string:")
47. text=input()
48. freqDict=defaultdict(int)
49.  
50. totalBitsBefore=0
51. for char in text:
52.     freqDict[char]+=1
53.     totalBitsBefore+=8
54.  
55. print("Char\tFreq\tCodes\tbit/char\t")
56. generateCodes(createHeap(freqDict))
57. totalBitsAfter=0
58. for node in leafNodes:
59.     bits=len(node.code)*freqDict[node.char]
60.     print(node.char,'\t',freqDict[node.char],'\t',node.code,'\t',bits)
61.     totalBitsAfter+=bits
62.  
63. print("\nTotal before: ",totalBitsBefore,"bits")
64. print("Total after: ",totalBitsAfter,"bits")
65. print("Saved: ",totalBitsBefore-totalBitsAfter,"bits")
66. #aaaaaaaaaaaabbcccccccdddddddddddddeeeeeeeeeeeeeefffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
67.