Priority Queue with Mutable Elements

[Josiah Carlson]

Chris Lasher wrote:
> I am working with large graphs (~150,000 to 500,000 nodes) which I
> need decompose node-by-node, in order of a node's value. A node's
> value is determined by the sum of its edge weights. When a node is
> removed from the graph, its neighbors' values must be updated to take
> into account the removed edges.
> 
> I was told to look for a priority queue in Python. I had a look at the
> heapq module. It looks like it supports ordering on insertion, but I'm
> unsure how to update the queue once a node's value changes.
> Additionally, I need the queue to be sorted on a particular attribute
> of the node objects, and don't see a way to do that other than
> override the __cmp__ method. Should I just use a list and use .sort()
> or sorted()? That seems like it could be horribly inefficient.
> 
> I found Andrew Snare's PQueue extension module [1] , which supports
> updating values in the priority queue by reassignment. It appeared to
> be broken in Python2.5 [2] but I found the offending line (a call to
> PyMem_DEL) and changed it (to PyObject_FREE) and it appears to be
> working fine. I would prefer to limit external depedencies for my
> modules, however.

See this implementation of a "pair heap":
   http://mail.python.org/pipermail/python-dev/2006-November/069845.html
...which offers the ability to update the 'priority' of an entry in the 
heap.  It requires that the 'value' in (priority, value) pairs be unique 
(to the heap) and hashable.

  - Josiah