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 :)