Here is my scenario. I want to implement A* (in Python) without having to resort to linear-time min or in operations. I need a heap to be able to efficiently get the lowest weight item.

My immediate response was 'Easy! I'll use heapq!' Then I discovered that life is rarely as simple as we would like it to be. It turns out that this strategy is suboptimal for one of the crucial points of A*. When consider children, I need to occasionally update the scores of the children already on the heap.

For those whose memory of A* has lapse a little, the gist of it is that I want to take an element, modify its weight, and modify the heap to reflect the change, all in sub-linear time.

Any suggestions?