Open In App

Priority Queue in Python

Last Updated : 29 Aug, 2022
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow

Priority Queues are abstract data structures where each data/value in the queue has a certain priority. For example, In airlines, baggage with the title “Business” or “First-class” arrives earlier than the rest.

Priority Queue is an extension of the queue with the following properties.

  1. An element with high priority is dequeued before an element with low priority.
  2. If two elements have the same priority, they are served according to their order in the queue.
    Various applications of the Priority queue in Computer Science are:
    Job Scheduling algorithms, CPU and Disk Scheduling, managing resources that are shared among different processes, etc.

Key differences between Priority Queue and Queue:

  1. In Queue, the oldest element is dequeued first. While, in Priority Queue, an element based on the highest priority is dequeued.
  2. When elements are popped out of a priority queue the result obtained is either sorted in Increasing order or in Decreasing Order. While, when elements are popped from a simple queue, a FIFO order of data is obtained in the result.

Below is a simple implementation of the priority queue.

Python




# A simple implementation of Priority Queue
# using Queue.
class PriorityQueue(object):
    def __init__(self):
        self.queue = []
 
    def __str__(self):
        return ' '.join([str(i) for i in self.queue])
 
    # for checking if the queue is empty
    def isEmpty(self):
        return len(self.queue) == 0
 
    # for inserting an element in the queue
    def insert(self, data):
        self.queue.append(data)
 
    # for popping an element based on Priority
    def delete(self):
        try:
            max_val = 0
            for i in range(len(self.queue)):
                if self.queue[i] > self.queue[max_val]:
                    max_val = i
            item = self.queue[max_val]
            del self.queue[max_val]
            return item
        except IndexError:
            print()
            exit()
 
if __name__ == '__main__':
    myQueue = PriorityQueue()
    myQueue.insert(12)
    myQueue.insert(1)
    myQueue.insert(14)
    myQueue.insert(7)
    print(myQueue)           
    while not myQueue.isEmpty():
        print(myQueue.delete()) 






                        










Output:


12 1 14 7
14
12
7
1




Note that the time complexity of delete is O(n) in the above code. A better implementation is to use Binary Heap which is typically used to implement a priority queue. Note that Python provides heapq in the library also.


Time complexity: By using heap data structure to implement Priority Queues
Insert Operation: O(log(n))
Delete Operation: O(log(n))





                                    


                                                                          

                                        

                                                                              

                                                                        

                                        

                                            

                                                

                                                    
O

        

            
        

        

                                                

                                                

                                                    Omkar Pathak                                                

                                            

                                            

            
                                        

                                        

                                            

                                                
                                                    News
                                                
                                            

                                            
    

        
        
    
                                            

                                                
                                                
                                            

                                            

                                            Improve
                                                
                                            

                                        

                                    



                            

                            
 
                                

                                    
                                        Next Article
                                        
                                    
                                    
                                    

                                        Multithreaded Priority Queue in Python
                                    

                                

                                                        

                        

                                                

                        
                                                    

                                
Similar Reads

                                

                                    
        
            

                
Should we declare as Queue or Priority Queue while using Priority Queue in Java?

                
Queue: Queue is an Interface that extends the collection Interface in Java and this interface belongs to java.util package. A queue is a type of data structure that follows the FIFO (first-in-first-out ) order. The queue contains ordered elements where insertion and deletion of elements are done at different ends. Priority Queue and Linked List are

            

            
            

                
                3 min read
            

        
    
        
            

                
What is Priority Queue | Introduction to Priority Queue

                
A priority queue is a type of queue that arranges elements based on their priority values. Elements with higher priority values are typically retrieved or removed before elements with lower priority values. Each element has a priority value associated with it. When we add an item, it is inserted in a position based on its priority value. There are

            

            
            

                
                15+ min read
            

        
    
        
            

                
Priority Queue using Queue and Heapdict module in Python

                
Priority Queue is an extension of the queue with the following properties. An element with high priority is dequeued before an element with low priority. If two elements have the same priority, they are served according to their order in the queue. queue.PriorityQueue(maxsize) It is a constructor for a priority queue. maxsize is the number of eleme

            

            
            

                
                3 min read
            

        
    

        
            

                
Why can't a Priority Queue wrap around like an ordinary Queue?

                
Priority Queue: A priority queue is a special type of queue in which each element is assigned a priority value. And elements are served based on their priority. This means that elements with higher priority are served first. However, if elements with the same priority occur, they will be served in the order in which they were queued. A priority que

            

            
            

                
                3 min read
            

        
    
        
            

                
Can we use Simple Queue instead of Priority queue to implement Dijkstra's Algorithm?

                
What is Dijkstra's Algorithm? Dijkstra's Algorithm is used for finding the shortest path between any two vertices of a graph. It uses a priority queue for finding the shortest path. For more detail, about Dijkstra's Algorithm, you can refer to this article. Why Dijkstra's Algorithm uses a Priority Queue? We use min heap in Dijkstra's Algorithm beca

            

            
            

                
                2 min read
            

        
    
        
            

                
Turn a Queue into a Priority Queue

                
What is Queue?Queue is an abstract data type that is open at both ends. One end is always used to insert data (enqueue) which is basically the rear/back/tail end and the other which is the front end is used to remove data (dequeue). Queue follows First-In-First-Out (FIFO) methodology, i.e., "the data item stored first will be accessed first". Decla

            

            
            

                
                9 min read
            

        
    
        
            

                
Why does Queue have front but Priority-queue has top in stl?

                
Why does the queue have front but the priority queue has top in stl? The main difference between a queue and a priority queue is that a queue follows the FIFO (First-In-First-Out) principle, while a priority queue follows a specific priority order. In other words, the elements in a queue are processed in the order they were added, whereas the eleme

            

            
            

                
                8 min read
            

        
    

        
            

                
Difference between Circular Queue and Priority Queue

                
Queues are fundamental data structures that are used to store and manage a collection of elements. While both circular queues and priority queues are types of queues, they have distinct characteristics and applications. This article will explore the key differences between circular queues and priority queues. Circular Queue:A Circular Queue is an e

            

            
            

                
                4 min read
            

        
    
        
            

                
Multithreaded Priority Queue in Python

                
The Queue module is primarily used to manage to process large amounts of data on multiple threads. It supports the creation of a new queue object that can take a distinct number of items. The get() and put() methods are used to add or remove items from a queue respectively. Below is the list of operations that are used to manage Queue: get(): It is

            

            
            

                
                2 min read
            

        
    
        
            

                
Heap and Priority Queue using heapq module in Python

                
Heaps are widely used tree-like data structures in which the parent nodes satisfy any one of the criteria given below. The value of the parent node in each level is less than or equal to its children's values - min-heap.The value of the parent node in each level higher than or equal to its children's values - max-heap. The heaps are complete binary

            

            
            

                
                5 min read
            

        
    
        
            

                
Priority Queue using Doubly Linked List

                
Given Nodes with their priority, implement a priority queue using doubly linked list. Prerequisite : Priority Queue push(): This function is used to insert a new data into the queue.pop(): This function removes the element with the lowest priority value from the queue.peek() / top(): This function is used to get the lowest priority element in the q

            

            
            

                
                11 min read
            

        
    
        
            

                
Does STL priority queue allow duplicate values?

                
Yes, in C++ priority_queue, we may have duplicate values. // C++ program to demonstrate that duplicate // values are allowed in a priority queue // (with maximum value at the top) #include <bits/stdc++.h> using namespace std; int main() { priority_queue<int> pq; pq.push(30); pq.push(5); pq.push(30); cout << pq.top() <<

            

            
            

                
                1 min read
            

        
    
        
            

                
Double ended priority queue

                
A double ended priority queue supports operations of both max heap (a max priority queue) and min heap (a min priority queue). The following operations are expected from double ended priority queue. getMax() : Returns maximum element.getMin() : Returns minimum element.deleteMax() : Deletes maximum element.deleteMin() : Deletes minimum element.size(

            

            
            

                
                6 min read
            

        
    

        
            

                
Implementation of Non-Preemptive Shortest Job First using  Priority Queue

                
Read here for Shortest Job First Scheduling algorithm for same arrival times.Shortest job first (SJF) or shortest job next, is a scheduling policy that selects the waiting process with the smallest execution time to execute next.In this article, we will implement the Shortest Job First Scheduling algorithm (SJF) using a priority queue, so that we c

            

            
            

                
                12 min read
            

        
    
        
            

                
Minimum Spanning Tree using Priority Queue and Array List

                
Given a bi-directed weighted (positive) graph without self-loops, the task is to generate the minimum spanning tree of the graph.Examples: Input: N = 9, E = 14, edges = {{0, 1, 4}, {0, 7, 8}, {1, 2, 8}, {1, 7, 11}, {2, 3, 7}, {2, 8, 2}, {2, 5, 4}, {3, 4, 9}, {3, 5, 14}, {4, 5, 10}, {5, 6, 2}, {6, 7, 1}, {6, 8, 6}, {7, 8, 7}} Output: ((A, B), Cost)

            

            
            

                
                5 min read
            

        
    
        
            

                
Huffman Coding using Priority Queue

                
Prerequisite: Greedy Algorithms | Set 3 (Huffman Coding), priority_queue::push() and priority_queue::pop() in C++ STL Given a char array ch[] and frequency of each character as freq[]. The task is to find Huffman Codes for every character in ch[] using Priority Queue. Example Input: ch[] = { 'a', 'b', 'c', 'd', 'e', 'f' }, freq[] = { 5, 9, 12, 13,

            

            
            

                
                12 min read
            

        
    
        
            

                
Find the K closest points to origin using Priority Queue

                
Given a list of n points on 2D plane, the task is to find the K (k < n) closest points to the origin O(0, 0). Note: The distance between a point P(x, y) and O(0, 0) using the standard Euclidean Distance. Examples: Input: [(1, 0), (2, 1), (3, 6), (-5, 2), (1, -4)], K = 3 Output: [(1, 0), (2, 1), (1, -4)] Explanation: Square of Distances of points

            

            
            

                
                7 min read
            

        
    

        
            

                
Merge two sorted arrays using Priority queue

                
Given two sorted arrays A[] and B[] of sizes N and M respectively, the task is to merge them in a sorted manner. Examples: Input: A[] = { 5, 6, 8 }, B[] = { 4, 7, 8 }Output: 4 5 6 7 8 8 Input: A[] = {1, 3, 4, 5}, B] = {2, 4, 6, 8} Output: 1 2 3 4 4 5 6 8 Input: A[] = {5, 8, 9}, B[] = {4, 7, 8} Output: 4 5 7 8 8 9 Approach: The given problem, mergin

            

            
            

                
                6 min read
            

        
    
        
            

                
Efficient way to initialize a priority queue

                
STL Priority Queue is the implementation of Heap Data Structure. By default, it's a max heap, and can be easily for primitive data types. There are some important applications of it which can be found in this article. Priority queue can be initialized in two ways either by pushing all elements one by one or by initializing using their constructor.

            

            
            

                
                7 min read
            

        
    
        
            

                
Indexed Priority Queue with Implementation

                
Priority queue is a data structure in which data is stored on basis of its priority. In an Indexed Priority Queue, data is stored just like standard priority queue and along with this, the value of a data can be updated using its key. It is called "indexed" because a hash map can be used to store the index in container using the key of key-value pa

            

            
            

                
                8 min read
            

        
    
        
            

                
Extracting last element of a Priority Queue without traversing

                
The Task is to extract the last element of the priority queue without traversing it. Approach: This problem can be solved using a Double-ended priority queue, a double-ended priority queue supports operations of both max heap (a max priority queue) and min heap (a min priority queue). The operations are: getMax(): Returns maximum element.getMin():

            

            
            

                
                7 min read
            

        
    
        
            

                
How to implement Priority Queue - using Heap or Array?

                
A Priority Queue is a data structure that allows you to insert elements with a priority, and retrieve the element with the highest priority. You can implement a priority queue using either an array or a heap. Both array and heap-based implementations of priority queues have their own advantages and disadvantages. Arrays are generally easier to impl

            

            
            

                
                15+ min read
            

        
    
        
            

                
Maximum Profit By Choosing A Subset Of Intervals (Using Priority-Queue)

                
Given a list intervals of n intervals, the ith element [s, e, p] denotes the starting point s, ending point e, and the profit p earned by choosing the ith interval. Find the maximum profit one can achieve by choosing a subset of non-overlapping intervals. Two intervals [s1, e1, p1] and [s2, e2, p2] are said to be non-overlapping if [e1 ? s2] and [s

            

            
            

                
                8 min read
            

        
    

        
            

                
STL Priority Queue for Structure or Class

                
STL priority_queue is the implementation of Heap Data-structure. By default, it's a max heap and we can easily use it for primitive datatypes. There are some important applications of it which can be found here Prerequisite: Prioirty_queue Basics In this article, we will see how can we use priority_queue for custom datatypes like class or structure

            

            
            

                
                3 min read
            

        
    
        
            

                
Priority queue of pairs in C++ with ordering by first and second element

                
Priority Queue: Priority queue is the extension of the queue in which elements associated with priority and elements having higher priority is popped first. Priority queue can contain elements with various data types such as integer, pair of integers, custom data type. But one thing is common that there is one element that defines the priority of t

            

            
            

                
                5 min read
            

        
    
        
            

                
Implementation of Priority Queue in Javascript

                
Priority Queue is an extension of Queue having some properties as follows: Each element of the priority queue has a priority associated with it.Elements are added to the queue as per priority.Lowest priority elements are removed first.We can design a priority queue using two approaches in the first case we can add the queue element at the end of th

            

            
            

                
                9 min read
            

        
    
        
            

                
Maximize array sum after K negations using Priority Queue

                
Given an array of size n and a number k. We must modify array K number of times. Here modify array means in each operation we can replace any array element arr[i] by -arr[i]. We need to perform this operation in such a way that after K operations, sum of array must be maximum? Examples: Input : arr[] = {-2, 0, 5, -1, 2} K = 4 Output: 10 // Replace

            

            
            

                
                5 min read
            

        
    

        
            

                
Multiple comparisons in a C++ priority queue?

                
What is a Priority Queue? A Priority Queue is an abstract data type that is similar to a queue, and every element has some priority value associated with it. The priority of the elements in a priority queue determines the order in which elements are served (i.e., the order in which they are removed). If in any case, the elements have the same prior

            

            
            

                
                5 min read
            

        
    
        
            

                
Implement the insert and delete functions on Priority queue without Array

                
A priority Queue is a type of queue in which every element is associated with a priority and is served according to its priority. We will use two popular data structures for implementing priority queues without arrays - Fibonacci HeapBinomial HeapFibonacci Heap:Fibonacci heap is a heap data structure that is composed of a collection of min-heap-ord

            

            
            

                
                15+ min read
            

        
    
        
            

                
How to implement stack using priority queue or heap?

                
How to Implement stack using a priority queue(using min heap)? Asked In: Microsoft, Adobe.  Solution: In the priority queue, we assign priority to the elements that are being pushed. A stack requires elements to be processed in the Last in First Out manner. The idea is to associate a count that determines when it was pushed. This count works as a k

            

            
            

                
                6 min read
            

        
                                    

                            

                        

                        

                                                            

                                    
Article Tags : 

                                    
                                                                            
                                                                    

                                                                                        

                                    
Practice Tags : 

                                    
                                                                            
                                                                    

                                                    

                                                

                                

                                    
                                                                    

                            


                        

                            

                                                                                    

                              

                            

                                                        
                        

                    

                

            

                

        

            

                

                    

                    
                
 
                
    
                            

                                

                            


                            


            

        
  

        

                




	
three90RightbarBannerImg

	
	

	
	

	
	    

	
	

	
	



                
        

    

    

        

            

            

        

    















	

    
  

  
  








    
        We use cookies to ensure you have the best browsing experience on our website. By using our site, you
        acknowledge that you have read and understood our
        Cookie Policy &
        Privacy Policy
            
    







   Lightbox