如何在Python中实现优先队列？

对不起，这是一个愚蠢的问题，但Python文档令人困惑。如何在Python中实现优先队列？

链接1：Queue实现 http://docs.python.org/library/queue.html

它说，这就是队列具有优先级队列contruct。但我找不到如何实现它。

class Queue.PriorityQueue(maxsize=0)

链接2：堆实现 http://docs.python.org/library/heapq.html

在这里，他们说，我们可以间接使用heapq

pq = []       # list of entries arranged in a heap 
entry_finder = {}    # mapping of tasks to entries 
REMOVED = '<removed-task>'  # placeholder for a removed task 
counter = itertools.count()  # unique sequence count 

def add_task(task, priority=0): 
    'Add a new task or update the priority of an existing task' 
    if task in entry_finder: 
     remove_task(task) 
    count = next(counter) 
    entry = [priority, count, task] 
    entry_finder[task] = entry 
    heappush(pq, entry) 

def remove_task(task): 
    'Mark an existing task as REMOVED. Raise KeyError if not found.' 
    entry = entry_finder.pop(task) 
    entry[-1] = REMOVED 

def pop_task(): 
    'Remove and return the lowest priority task. Raise KeyError if empty.' 
    while pq: 
     priority, count, task = heappop(pq) 
     if task is not REMOVED: 
      del entry_finder[task] 
      return task 
    raise KeyError('pop from an empty priority queue'

在Python里是最有效的优先级队列实现实现优先级队列？以及如何实施它？

来源

2012-04-01 codersofthedark

[Python的一个普通优先级队列（可能的重复http://stackoverflow.com/questions/407734/a-generic-priority-queue -for-python） – 2017-05-17 14:22:11

版本在队列模块是implemented使用heapq模块，因此它们对底层堆操作具有相同的效率。

也就是说，队列版本比较慢，因为它增加了锁，封装和一个很好的面向对象的API。

priority queue suggestions shown in the heapq docs旨在说明如何向优先队列添加附加功能（例如排序稳定性和改变先前入队任务的优先级的能力）。如果你不需要这些功能，那么基本的功能将会带给你最快的性能。

来源

2012-04-02 00:05:34

谢谢..那是我想知道的 - :) – codersofthedark 2012-04-02 06:56:06

任何语言都没有“最有效的优先级队列实现”这样的东西。

优先级队列全是关于折衷。见http://en.wikipedia.org/wiki/Priority_queue

你应该选择这两个中的一个，根据您打算如何使用它：

O(log(N))插入时间和O(1) findMin + deleteMin时间，或
O(1)插入时间和O(log(N)) findMin + deleteMin time

在后一种情况下，你可以选择实现一个斐波那契堆优先级队列：http://en.wikipedia.org/wiki/Heap_(data_structure)#Comparison_of_theoretic_bounds_for_variants（如y OU可以看到，heapq这基本上是一个二叉树，必然有O(log(N))的插入和findMin + deleteMin）

如果你正在处理的具有特殊性能数据（如边界数据），那么就可以实现O(1)插入和O(1) findMin + deleteMin时间。您只能对某些类型的数据执行此操作，否则您可能会滥用您的优先队列来违反排序时绑定的O(N log(N))。

要实现任何语言的任何队列，您只需要定义insert(value)和extractMin() -> value操作。这通常只涉及对基础堆的最小包装;看到http://en.wikipedia.org/wiki/Fibonacci_heap实现自己的，或者使用类似的堆像配对堆的一个现成的，现成的库（谷歌搜索显示http://svn.python.org/projects/sandbox/trunk/collections/pairing_heap.py）

如果你只关心这两个，你引用的是更有效（的heapq基于从http://docs.python.org/library/heapq.html#priority-queue-implementation-notes您在上面包括，对Queue.PriorityQueue代码），则：

似乎有不为，什么Queue.PriorityQueue实际上是在网上做任何易容易找到的讨论;你将不得不采购潜入代码，这是与从帮助文档：http://hg.python.org/cpython/file/2.7/Lib/Queue.py

224  def _put(self, item, heappush=heapq.heappush): 
    225   heappush(self.queue, item) 
    226 
    227  def _get(self, heappop=heapq.heappop): 
    228   return heappop(self.queue)

正如我们所看到的，Queue.PriorityQueue也使用heapq作为底层机制。因此它们同样不好（渐近地说）。 Queue.PriorityQueue可能允许并行查询，所以我敢打赌它可能会有一个非常小的常数因子更多的开销。但是因为您知道底层实现（和渐近行为）必须相同，所以最简单的方法就是在同一个大型数据集上运行它们。

（请注意，Queue.PriorityQueue似乎没有办法删除条目，而heapq却可以。但是这是一把双刃剑：优先级队列实现可能允许您删除O（1）或O（log（N））时间，但是如果你使用你提到的remove_task函数，并且让这些僵尸任务在你的队列中积累，因为你没有从min中提取它们，那么你会看到渐进式减速，你不会否则看到的。当然，你无法Queue.PriorityQueue摆在首位做到这一点，所以没有比较可以在此处进行。）

来源

2012-04-01 23:38:00 ninjagecko

我在理论上拒绝优先级队列很好，因此可能的DS。但问题是关于它在Python中的实现，它具有非常不同的DS集合。 – codersofthedark 2012-04-01 23:45:51

@dragosrsupercool：“DS”？ – ninjagecko 2012-04-01 23:48:46

数据结构..。 – codersofthedark 2012-04-01 23:57:26

虽然这个问题已被回答并被标记为接受，但仍然是一个简单的自定义实现的优先级队列，无需使用任何模块来了解其工作原理。

# class for Node with data and priority 
class Node: 

    def __init__(self, info, priority): 
    self.info = info 
    self.priority = priority 

# class for Priority queue 
class PriorityQueue: 

    def __init__(self): 
    self.queue = list() 
    # if you want you can set a maximum size for the queue 

    def insert(self, node): 
    # if queue is empty 
    if self.size() == 0: 
     # add the new node 
     self.queue.append(node) 
    else: 
     # traverse the queue to find the right place for new node 
     for x in range(0, self.size()): 
     # if the priority of new node is greater 
     if node.priority >= self.queue[x].priority: 
      # if we have traversed the complete queue 
      if x == (self.size()-1): 
      # add new node at the end 
      self.queue.insert(x+1, node) 
      else: 
      continue 
     else: 
      self.queue.insert(x, node) 
      return True 

    def delete(self): 
    # remove the first node from the queue 
    return self.queue.pop(0) 

    def show(self): 
    for x in self.queue: 
     print str(x.info)+" - "+str(x.priority) 

    def size(self): 
    return len(self.queue)

找到完整的代码，并解释在这里：https://www.studytonight.com/code/python/algo/priority-queue-in-python.php

来源

2018-02-28 07:10:19 iamabhishek

如何在Python中实现优先队列？

回答

相关问题