[queue] Implementing Priority Queue in Python

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. Implementing 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, -1): 
            self._heapify(len(self.queue), i)

 

3. Proirity Queue with Library

Python offer module for implementing queue. The queue module implements multi-producer, multi-consumer queues. Thereare some methods can use commonly.

 

from queue import PriorityQueue

queue = PriorityQueue()

 

• 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 without delay.
• queue.pop() : Pop element from queue and return it.
• queue.get_nowait() : Pop element from queue without delay.

 

 

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