從優先級隊列中刪除項目

在Python中，heapq模塊提供了一個優先級隊列。從優先級隊列中刪除項目

它有插入和彈出項目的方法。

如何從隊列中移除您插入的不是最低優先級的項目？

（這樣做使用替代其他收藏品替代的食譜也歡迎）

2011-03-30 Will

的heapq模塊採用標準的Python列表作爲底層的數據結構，所以你可以在此之後只使用標準list方法remove()和heapify()一次。請注意，這將需要線性時間。

# Create example data and heapify 
a = range(10) 
a.reverse() 
heapq.heapify(a) 
print a 

# remove an element and heapify again 
a.remove(5) 
heapq.heapify(a) 
print a

你可以提高使用無證功能heapify._siftup()再次heapifying的表現，但整個過程仍然會因爲list.remove() O（n）是O（N）。

來源

2011-03-30 10:15:28

但是這會破壞堆不變？ – Will 2011-03-30 10:17:32

@ will：heapify（）恢復不變量。 – Macke 2011-03-30 10:19:21

@Will，Macke：對不起，我很困惑。我首先發布了一個沒有提到你必須再次調用'heapify（）'的版本，但立即糾正了它。 – 2011-03-30 10:29:36

有一個數據結構稱爲treap這是一個優先級隊列和二叉樹的組合。（樹堆）。它允許日誌搜索，這可能會幫助你。

有一個Python treap implementation on PyPi ..;）

來源

2011-03-30 10:17:46 Macke

該日誌（N）函數的工作對我來說：

def heapq_remove(heap, index): 
    """Remove item from heap""" 

    # Move slot to be removed to top of heap 
    while index > 0: 
     up = (index + 1)/2 - 1 
     heap[index] = heap[up] 
     index = up 

    # Remove top of heap and restore heap property 
    heapq.heappop(heap)

來源

2012-01-20 16:21:42

如果你知道你要刪除的項目的位置，你可以做以下：現在

a[k] = a.pop() 
heapq.heapify(a)

第一步是O（1）時間，並且第二可通過使用未記錄的數據進行O（日誌（N））。當然，如果你還沒有找到k，它仍然是O（N）。

來源

2012-03-22 03:02:02 Stephen

您可以使用Python的對分模塊在O（log（N））時間中查找k，這將使得整個解決方案O（log（N））。 – javawizard 2012-07-23 00:30:45

@javawizard對不起，但我沒有得到你，我怎麼才能找到堆中的元素的位置/索引？我正在考慮維護字典，但是每次插入堆時，我都必須修改該字典。 – Naman 2014-09-13 18:54:39

小心，a [k] = a.pop（）不適用於列表中的最後一個元素 – gizzmole 2017-11-27 15:39:57

從優先級隊列中刪除項目

回答

相關問題