First - Simulate Priority Queue clear solution for Huffman Encode by U.V - python coding challenges

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:

przemyslaw.daniel on Jan. 17, 2023, 11:44 a.m.
Priority queue is available on checkio, it's called heapq. What you use here is a thread safe version which is not necessary. In case of an own implementation of priority queue, I can see two drawbacks. The very first one is sorting which takes place when an element is put, and the second one is when an element is extracted. Pop from the left hand side causes an entire list to be shifted which is also costly. The original implementation of priority queue is a bit complicated, but we can have simple version (less efective than original but with easy code) by eliminating these two issues, For example <pre class='brush: python'>class PriorityQueue: def __init__(self): self.pq = [] def swap(self, a, b): self.pq[a], self.pq[b] = self.pq[b], self.pq[a] def get(self): self.swap(self.pq.index(min(self.pq)), len(self.pq) - 1) return self.pq.pop() def put(self, item): self.pq.append(item) </pre> What do you think? BTW: in principle your solution is very similar to mine

U.V on Jan. 18, 2023, 11:35 a.m.
This simulation of PQ is fine too. Interface to PQ in my mind is clearer then that of heapq. In production, we should prefer a heapq, but sorting of short array and long text is not main time consumption process ( i think B-)

Strings Theory

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.