Let’s go over our priority queue implementation. The reason for using heapq instead of other data types is that you can push and pop in O(log n) time while keeping the underlying data in order of priority. We’ll use the heapq available from the Lib/heapq.py module in Python for our priority queue implementation. pq.is_empty(): returns True if the priority queue is empty.pq.size(): returns the number of task in the priority queue.pq.peek(): returns the highest priority task from the priority queue.pq.pull(): returns and removes the highest priority task from the priority queue.pq.insert(task, priority): adds a task with a given priority to the priority queue.Most priority queue implementations have the following methods: They are also used in bandwidth management to prioritize important data packets.Ĭertain foundational algorithms, such as Dijkstra’s algorithm, also rely on priority queues. Operating systems use priority queues to select the following process to run, load balancing and interrupt handling. In a max-priority queue, you assign a higher priority to a task with a higher priority number.In a min-priority queue, you assign a higher priority to a task with a lower priority number.While the next element in a queue is the first element inserted and in a stack is the last element inserted, in a priority queue, the next element to be retrieve is the one with the highest priority. Priority queues differ from queues and stack in the way your retrieve the elements. In computer science, a priority queue is an abstract data type in which each element has a priority associated with it. A Priority Queue Implementation in Python (this article).I based the series on my notes while studying for a Python technical interview.įor quick access, here is the list of posts on this series: This post is the third in a miniseries exploring the implementation of linear data structures. In this article, I’ll explore the priority queue, a linear data structure we can easily implement in Python.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |