Heap that supports modification of its elements?

Question

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?

Answer 1

For complexity purposes, you would want to try a binomial or Fibonacci heap; it appears that there are implementations of both in Python but not production-grade libraries. A binary or d-ary heap might work faster in practice, though. The heapq page mentions how to do updates (keep a reference to the item that you insert into the heap, mark it as invalid and then insert a new version). There are faster algorithms for maintaining the heap property after updates, though. Look at http://en.wikipedia.org/wiki/D-ary_heap for the algorithms to use for fast updates, but you would probably need to implement your own heap on top of an array for those.

Answer 2

It's true, neither the heap functions in heapq nor Queue.PriorityQueue are very functional. It probably takes about equal time to either A: write a rant on your blog or B: implement one yourself.

Answer 3

I always end up implementing my own version of a Heap type, for the exact reason that you can't actually search in a Heap, while all efficient methods require "a pointer to the element" as input.

Usually, I implement my Heap as a combination of an unstructured container of Items, and a Heap of pointers (or indeces) to Items. If you keep a pointer to a Heap location in the Item, you have an immediate two-way link: a) Given a Heap element (e.g. returned by extractMin, or during a comparison): dereference the pointer, and you've got your item. b) Given an Item (e.g. through an adjacency list of a Graph algorithm): pass the pointer to whatever update function you want.

Of course, this causes space overhead (2 additional pointers/integers per Item), but it makes Heap restructuring very cheap (swapping a few pointers instead of swapping entire Items), which in return makes it less painful to add some additional satellite data to your Items.