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

Answer 5

If you don't want an O(n) routine you need to use internal _siftup and _siftdown (yes you need to use both because after the swap the element may need swim down as it may need to float up). You decide if that's deterrent for you or not, but here it goes.

import heapq

# The removal function using internal functions
def remove_item(heap, val):
    if not heap:
        return

    try:
        i = heap.index(val)
    except ValueError:
        return

    if i < len(heap) - 1:
        heap[i] = heap[-1]

    heap.pop()
    if i < len(heap):
        heapq._siftup(heap, i)
        heapq._siftdown(heap, 0, i)


# Initial state
a = range(30)
a.reverse()
heapq.heapify(a)
print(a)

# The removal
remove_item(a, 15)
print(a)

Kudos to Duncan: https://stackoverflow.com/a/10163422/292502

Answer 6

had this problem on my project using search algorithms, here is the answer:

queue_name = PriorityQueue()

queue_name.queue.remove(item_to_be_removed)

Say you had a tuple as an item then an example would be:

queue_name.queue.remove((number, item_name))