Given An array of Alphabets and their frequency. Your task is to print all the given alphabets Huffman Encoding.
Note: If two elements have same frequency, then the element which if at first will be taken on left of Binary Tree and other one to right. Input: First line consists of test cases T. First line of every test case consists of string of alphabets and second line consists of its frequencies. Output: Print the HuffmanCodes in single line, with n spaces of each alphabet's HuffmanCodes respectively. In PreOrder form of Binary Tree. Constraints: 1<=T<=100 1<=|String length|<=26
1 abcdef 5 9 12 13 16 45 | [0, 100, 101, 1100, 1101, 111] |
1 abcdef 5 9 13 21 61 45 | [0 |
Tags languages PYTHON
Subscribe Our Newsletter
.jpg "SABAREESH R")
import queue
ReplyDeleteclass HuffmanNode(object):
def __init__(self, left=None, right=None, root=None):
self.left = left
self.right = right
self.root = root
def children(self):
return((self.left, self.right))
a=input()
b=input()
c=input()
d=c.split()
freq=[]
freq1=[]
l1=[]
l2=[eval(x) for x in d]
for x in range(len(b)):
l1.append(b[x])
for x in range(len(l1)):
freq1.append([])
for y in range(0,1):
freq1[x].append(l2[x])
for x in range(len(l1)):
for y in range(0,1):
freq1[x].append(l1[x])
freq.append(tuple(freq1[x]))
def create_tree(frequencies):
p = queue.PriorityQueue()
for value in frequencies:
p.put(value)
while p.qsize() > 1:
l, r = p.get(), p.get()
node = HuffmanNode(l, r)
p.put((l[0]+r[0], node))
return p.get()
node = create_tree(freq)
def walk_tree(node, prefix="", code={}):
if isinstance(node[1].left[1], HuffmanNode):
walk_tree(node[1].left,prefix+"0", code)
else:
code[node[1].left[1]]=prefix+"0"
if isinstance(node[1].right[1],HuffmanNode):
walk_tree(node[1].right,prefix+"1", code)
else:
code[node[1].right[1]]=prefix+"1"
return(code)
code = walk_tree(node)
#print(l)
#print(code)
l3=[]
for j in code.values():
l3.append(eval(j))
print(l3)