How can I implement decrease-key functionality in Python's heapq?

To implement "decrease-key" effectively, you'd need to access the functionality "decrement this element AND swap this element with a child until heap condition is restore". In heapq.py, that's called _siftdown (and similarly _siftup for INcrementing). So the good news is that the functions are there... the bad news is that their names start with an underscore, indicating they're considered "internal implementation details" and should not be accessed directly by application code (the next release of the standard library might change things around and break code using such "internals").

It's up to you to decide whether you want to ignore the warning leading-_, use O(N) heapify instead of O(log N) sifting, or reimplement some or all of heapq's functionality to make the sifting primitives "exposed as public parts of the interface". Since heapq's data structure is documented and public (just a list), I think the best choice is probably a partial-reimplementation -- copy the sifting functions from heapq.py into your application code, essentially.

Decrease-key is a must-have operation for many algorithms (Dijkstra's Algorithm, A*, OPTICS), i wonder why Python's built-in priority queue does not support it.

Unfortunately, i wasn't able to download math4tots's package.

But, i was able to find this implementation by Daniel Stutzbach. Worked perfectly for me with Python 3.5.

hd = heapdict()
hd[obj1] = priority
hd[obj1] = lower_priority
# ...
obj = hd.pop()

The heapq documentation has an entry on exactly how to do this.

However, I have written a heap package that does exactly this (it is a wrapper around heapq). So if you have pip or easy_install you could do something like

pip install heap

Then in your code write

from heap.heap import heap

h = heap()

h['hello'] = 4 # Insert item with priority 4.

h['hello'] = 2 # Update priority/decrease-key has same syntax as insert. 

It is pretty new though, so might be full of bugs.