[Python-ideas] Heap data type
jh at improva.dk
Sat Apr 18 15:28:00 CEST 2009
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
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
More information about the Python-ideas