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

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)