如何在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中實現優先隊列？

回答

相關問題