Removing an item from a priority queue

Question

In Python, the heapq module provides a priority queue.

It has methods for inserting and popping items.

How do you remove an item that you have inserted that is not the lowest priority from the queue?

(Alternative recipes for doing this using alternative other collections are welcome too)

Answer 1

The heapq module uses standard Python lists as underlying data structure, so you can just use the standard list method remove() and heapify() again after this. Note that this will need linear time though.

# 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

You could improve the performance of heapifying again by using the undocumented function heapify._siftup(), but the whole process will still be O(n) since list.remove() is O(n).