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).

Answer 2

If you know the location of the item you wish to remove, you can do the following:

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

The first step is now O(1) time, and the second can be made O(log(N)) by using the undocumented data. Of course, it's still O(N) to find k if you don't have it already.

Answer 3

This log(N) function works for me:

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)

Answer 4

There is a data structure called a treap which is a priority queue and binary tree combined. (tree-heap). It allows for log-n search which might help you.

There's a Python treap implementation on PyPi.. ;)