[Python-Dev] heaps

Agthorr agthorr@barsoom.org
Thu, 24 Apr 2003 13:48:12 -0700


I brought up heapq last week, but there was only brief discussion
before the issue got sidetracked into a discussion of FIFO queues.
I'd like to revisit heapq.  The two people who responded seemed to
agree that the existing heapq interface was lacking, and this seemed
to be the sentiment many months ago when heapq was added.

I'll summarize some of the heap interfaces that have been proposed:

 - the heapq currently in CVS:
   - Provides functions to manipulate a list organized as a binary heap
   - Advantages:
     - Internal binary heap structure is transparent to user, useful
       for educational purposes
     - Low overhead
     - Already in CVS

 - My MinHeap/MaxHeap classes:
   - Provides a class with heap access routines, using a list internally
   - Advantages:
     - Implementation is opaque, so it can be replaced later with
       Fibonacci heaps or Paired heaps without breaking user programs
     - Provides an adjust_key() command needed by some applications
       (e.g. Dijkstra's Algorithm)

 - David Eppstein's priorityDictionary class:
   - Provides a class with a dictionary-style interface
     (ex: heap['cat'] = 5 would give 'cat' a priority of 5 in the heap)
   - Advantages:
     - Implementation is opaque, so it can be replaced later with
       Fibonacci heaps or Paired heaps without breaking user programs
     - A dictionary interface may be more intuitive for certain
       applications
   - Limitation:
     - Objects with the same value may only have a single instance in
       the heap.

I'd very much like to see the current heapq replaced with a different
interface in time for 2.3.  I believe that an opaque object is better,
since it allows more flexibility later.  If the current heapq is
released, user program will start to use it, and then it will be much
more difficult to switch to a different heap algorithm later, should
that become desirable.  Also, decrease-key is an important feature
that many users will expect from a heap; this operation is notably
missing from heapq.

I'm willing to do whatever work is necessary to get a more flexible
heap interface into 2.3.  If the consensus prefers my MinHeap (or
something similar), I'll gladly write documentation (and have already
written rather brutal tests).

Somebody with authority, just tell me where to pour my energy in this
matter :)

-- Agthorr