[Python-ideas] Heap data type

[Jacob Holm]

Facundo Batista wrote:
> Using the module heapq, I found that it's not easy to use. Or, at
> least, that it could be straightforward to use.
> 
> My main issue is that for correct usage:
> 
> - user should provide an external list, that shouldn't use for
> anything else to don't break the invariant
> 
> - to alter the heap queue, a bunch of functions must be used, passing
> always the external list
> 
> 
> I think that changing "external list" for "internal attribute", and
> "bunch of functions " for "methods", it will leave the module easier
> to use, safer, and more object oriented.
> 
> So, I basically coded it. What do you think about including this class
> in the heap module?
> 

Your "Heap" class implements (part of) an abstract data type usually 
known as a priority queue.

The fact that it uses the heapq module internally is an implementation 
detail that is not (and should not be IMHO) exposed to the users of the 
class.  So if this is added, I think it should rather go in the 
collections module.

Much better (faster for some operations) implementations of this ADT are 
possible, so by not tying the implementation to heapq we would be free 
to switch the implementation later if we want.


+1 to adding a collections.priority_queue, initially based on your class.

+0 to adding your class as heapq.Heap


In either case I think you should add at least the following additional 
method.

   def peek(self):
       return self._queue[0]


- Jacob