[DS] Queue

1. What is Priority Queue ?

A priority queue is a special type of queue in which each element is associated with a priority value. And, elements are served on the basis of their priority.

 

Generally, the value of the element itself is considered for assigning the priority. For example, the element with the highest value is considered the highest priority element.

2. Inplementation of Priority Queue

class PriorityQueue: 
    def __init__(self): 
        self.queue = [] 
        
    def _heapify(self, n, i): 
        largest = i
        l = 2 * i + 1
        r = 2 * i + 2 
        
        if l < n and self.queue[i] < self.queue[l]:
            largest = l
        if r < n and self.queue[largest] < self.queue[r]: 
            largest = r 
            
        if largest != i: 
            self.queue[i], self.queue[largest] = self.queue[largest], self.queue[i]
            self._heapify(n, largest)
            
    def insert(self, new):
        size = len(self.queue)
        if size == 0 : 
            self.queue.append(new) 
        else : 
            self.queue.append(new)
            for i in range((size // 2) - 1, -1, -1): 
                self._heapify(size, i) 
                
    def deleteNode(self, num):
        size = len(self.queue)
        i = 0
        for i in range(0, size):
            if num == self.queue[i]:
                break
        self.queue[i], self.queue[size - 1] = self.queue[size - 1], self.queue[i]
        self.queue.remove(size - 1)
        for i in range((len(self.queue) // 2) - 1, -1

 

3. Library of Priority Queue

Python offer module of queue. The queue module implements multi-producer, multi-consumer queues. There are some methods can use commonly.

from queue import Queue, LifoQueue, PrioriyQueue

 

• Queue.qsize() : Returns the size of queue.
• Queue.empty() : Return True if queue is empty, False if not.
• Queue.put(item) : Push item to queue.
• Queue.put_nowait(item) : Work same as put(item, False)
• Queue.get() : Pop element from queue and return it.
• Queue.get_nowait() : Work same as queue(item, False)

 

 

https://docs.python.org/ko/3.7/library/queue.html

queue — 동기화된 큐 클래스 — Python 3.7.13 문서