Python heapq replace priority

Question

I'm trying to implement Dijkstra's algorithm using Python's heapq. The algorithm requires changing a cell's value if a shorter path is discovered leading to it.

I'm doing that with this check:

if curr_cell[0] + val < prev_cell[0]:  # value of new path is less than old value
    new_cell = (curr_cell[0] + val, prev_cell[1], curr_cell[1])
    heap[index] = new_cell
    heapify(heap)

However, when running my program on a larger maze this is taking a long time, probably because of the heapify() call.

What's a more efficient way of changing the priority of a heap's entry?

Answer 1

The heapq library doesn't support updating priorities efficiently because there is no efficient way to search the heap. If you search the heap in O(n) time and manually replace the element, you can then use _siftup() and _siftdown() to restore the heap invariant.

Alternatively, here is a compatible implementation I wrote which uses a dict to allow O(1) lookups of heap indexes.

https://github.com/elplatt/python-priorityq

Answer 2

A possible solution is to mark the entry as removed and add a new entry with the revised priority. The documentation provides an example implementation:

pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task
counter = itertools.count()     # unique sequence count

def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')