Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First - Simulate Priority Queue solution in Clear category for Huffman Encode by U.V
from collections import Counter, defaultdict
try:
from queue import PriorityQueue
except Exception as ex:
print(ex)
print("The module `queue` is not allowed on checkio. Simulate PriorityQueue B-)")
class PriorityQueue():
def __init__(self):
self.pq = []
def get(self):
return self.pq.pop(0)
def put(self, item):
self.pq.append(item)
self.pq.sort()
def qsize(self):
return len(self.pq)
def __repr__(self):
return(str(self.pq))
def huffman_encode(s: str) -> str:
cnt = Counter(s)
huff = defaultdict(str)
q = PriorityQueue()
if len(cnt) == 1:
huff[s[0]] = '0'
for k, v in cnt.items():
q.put((v, k))
while q.qsize() > 1:
k1,v1 = q.get()
k2,v2 = q.get()
k = k1 + k2
v = v1 + v2
for l in v1:
huff[l] = '0' + huff[l]
for l in v2:
huff[l] = '1' + huff[l]
q.put((k, v))
return ''.join(huff[c] for c in s)
Jan. 16, 2023
Comments:
