从优先级队列中删除项目

在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

从优先级队列中删除项目

回答

相关问题