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

I know it is possible to realize decrease-key functionality in O(log n) but I don’t know how?

Answer

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.