﻿ python - Heap that supports modification of its elements? - Oipapio- oipapio.com

# python - 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?

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.

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.

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.