Last updated on 2024年3月20日

What is the Python code for implementing a priority queue?

由人工智能和领英社区提供技术支持

A priority queue is a data structure that stores and retrieves elements based on their priority, which is usually a numerical value or a comparison function. Priority queues are useful for applications that need to process items in a certain order, such as scheduling tasks, routing packets, or finding the shortest path. In this article, you will learn how to implement a priority queue in Python using two different approaches: a list and a heap.

此文章中的业界达人

由社区从 2 条内容中精选。了解更多

Harsha vardhan Boora

SDE INTERN @FACTTWIN||SOFTWARE ENGINEER INTERN @AEGION DYNAMIC SOLUTIONS || DSA THROUGH GO,SWIFT ||TCW @GEEKS FOR…

1 List approach

One way to implement a priority queue in Python is to use a list as the underlying data structure. The list can store tuples of (priority, item) pairs, where the priority is a number that determines the order of retrieval. To insert an element, you can use the append() method to add it to the end of the list. To remove an element, you can use the pop() method to remove the first element of the list after sorting it by priority. This approach is simple and intuitive, but it has some drawbacks. Sorting the list every time you remove an element can be inefficient, especially if the list is large or the priorities change frequently. Here is an example of how to implement a priority queue using a list:

# Define a class for the priority queue
class PriorityQueue:
  # Initialize the list
  def __init__(self):
    self.items = []
  # Check if the queue is empty
  def is_empty(self):
    return len(self.items) == 0
  # Insert an element with a given priority
  def insert(self, item, priority):
    self.items.append((priority, item))
  # Remove and return the element with the highest priority
  def remove(self):
    # Sort the list by priority in descending order
    self.items.sort(reverse=True)
    # Pop and return the first element of the list
    return self.items.pop()[1]
# Create an instance of the priority queue
pq = PriorityQueue()
# Insert some elements with different priorities
pq.insert("A", 3)
pq.insert("B", 1)
pq.insert("C", 2)
# Remove and print the elements in order of priority
while not pq.is_empty():
  print(pq.remove())

添加您的观点

Harsha vardhan Boora

SDE INTERN @FACTTWIN||SOFTWARE ENGINEER INTERN @AEGION DYNAMIC SOLUTIONS || DSA THROUGH GO,SWIFT ||TCW @GEEKS FOR GEEKS||CSE DATA SCIENCE 2025
举报内容
from functools import cmp_to_key class Pair: def __init__(self,a,b): self.a=a;self.b = b def compare(obj1,obj2): if obj1.b <obj2.b: return -1 if obj1.b == obj2.b: return 0 return 1 class PriorityQueue: def __init__(self,array,size): self.size = size;self.array=array;self.new_list=[] def push(self,data,priority): if len(self.array)==self.size:print("Priority queue is empty");return self.array.append((data,priority));self.new_list=[ Pair(i[0],i[1]) for i in self.array ] self.new_list=sorted(self.new_list,key = cmp_to_key(Pair.compare)) obj = PriorityQueue([],5);obj.push("A",1);obj.push("B",3);obj.push("C",2) push function using comparator ...

已翻译

赞

2 Heap approach

Another way to implement a priority queue in Python is to use a heap as the underlying data structure. A heap is a binary tree that satisfies the heap property: the value of each node is greater than or equal to the value of its children. A heap can efficiently store and retrieve the element with the highest value, which corresponds to the highest priority in a priority queue. To insert an element, you can use the heappush() function from the heapq module to add it to the heap. To remove an element, you can use the heappop() function from the heapq module to remove and return the root of the heap. This approach is more efficient and scalable than the list approach, as it does not require sorting the entire data structure every time you remove an element. However, it requires some modifications to work with tuples of (priority, item) pairs, as the heapq module only supports min-heaps, where the lowest value has the highest priority. To reverse this order, you can use negative priorities or swap the order of the tuple elements. Here is an example of how to implement a priority queue using a heap:

# Import the heapq module
import heapq
# Define a class for the priority queue
class PriorityQueue:
  # Initialize the heap
  def __init__(self):
    self.items = []
  # Check if the queue is empty
  def is_empty(self):
    return len(self.items) == 0
  # Insert an element with a given priority
  def insert(self, item, priority):
    # Use negative priority or swap the order of the tuple elements
    heapq.heappush(self.items, (-priority, item))
  # Remove and return the element with the highest priority
  def remove(self):
    # Use negative priority or swap the order of the tuple elements
    return heapq.heappop(self.items)[1]
# Create an instance of the priority queue
pq = PriorityQueue()
# Insert some elements with different priorities
pq.insert("A", 3)
pq.insert("B", 1)
pq.insert("C", 2)
# Remove and print the elements in order of priority
while not pq.is_empty():
  print(pq.remove())

添加您的观点

3 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?

添加您的观点

Ujjwal Tyagi

SDE || BDO in India
举报内容
To implement priority queue in Python, one may use heapq module, which provides heapq algorithm functions. Overall, this implementation using the heapq module strikes a balance between efficiency, simplicity, and flexibility, making it suitable for many use cases. However, it’s important to consider its limitations, especially if frequent priority updates are expected.

已翻译

赞

Programming

+ 关注

给文章评分

我们借助人工智能创建了此文章。您认为这篇文章怎么样？

很棒不太好

举报此文章

查看全部

What is the Python code for implementing a priority queue?

1

2

3

1 List approach

2 Heap approach

3 Here’s what else to consider

Programming

给文章评分

感谢您的反馈

更多Programming相关文章

更多相关阅读内容

What is the Python code for implementing a priority queue?

1

2

3

1 List approach

2 Heap approach

3 Here’s what else to consider

Programming

给文章评分

感谢您的反馈

查看其他技能