- Notifications
You must be signed in to change notification settings - Fork 366
/
Copy pathHuffmanCodingAlgo.py
53 lines (31 loc) · 900 Bytes
/
HuffmanCodingAlgo.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
importheapq
classnode:
def__init__(self, freq, symbol, left=None, right=None):
self.freq=freq
self.symbol=symbol
self.left=left
self.right=right
self.huff=''
def__lt__(self, nxt):
returnself.freq<nxt.freq
defprintNodes(node, val=''):
newVal=val+str(node.huff)
if(node.left):
printNodes(node.left, newVal)
if(node.right):
printNodes(node.right, newVal)
if(notnode.leftandnotnode.right):
print(f"{node.symbol} -> {newVal}")
chars= ['a', 'b', 'c', 'd', 'e', 'f']
freq= [ 4, 7, 12, 14, 35, 72]
nodes= []
forxinrange(len(chars)):
heapq.heappush(nodes, node(freq[x], chars[x]))
whilelen(nodes) >1:
left=heapq.heappop(nodes)
right=heapq.heappop(nodes)
left.huff=0
right.huff=1
newNode=node(left.freq+right.freq, left.symbol+right.symbol, left, right)
heapq.heappush(nodes, newNode)
printNodes(nodes[0])
