[Python-ideas] Heap data type

Gerald Britton gerald.britton at gmail.com
Mon Apr 20 15:01:21 CEST 2009

Raymond, Facundo,

May I suggest that you implement an interface similar to the sort()
method for list objects:
sort([cmp[, key[, reverse]]])

"cmp specifies a custom comparison function of two arguments (list
items) which should return a negative, zero or positive number
depending on whether the first argument is considered smaller than,
equal to, or larger than the second argument: cmp=lambda x,y:
cmp(x.lower(), y.lower()). The default value is None.

"key specifies a function of one argument that is used to extract a
comparison key from each list element: key=str.lower. The default
value is None.

"reverse is a boolean value. If set to True, then the list elements
are sorted as if each comparison were reversed."

You could add these option arguments to the Heap class constructor,
which would then be used to maintain the heap.  The _reverse_ argument
would cover the min/max heap question.  The other arguments would
allow the user to use the class for a priority queue of more complex
objects.  For example, the Heap could consist of object references
that would be compared using the function supplied in _cmp_ or _key_

On Sat, Apr 18, 2009 at 7:40 PM, Raymond Hettinger <python at rcn.com> wrote:
> Facundo, I would like to work with you on this.
> I've been the primary maintainer for heapq for a while
> and had already started working on something like this
> in response to repeated requested to support a key= function
> (like that for sorted/min/max).
> Raymond
>>> 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.
>> +1 -- I recently did a short presentation on Big O notation and Python
>> containers, and heapq looked remarkably ugly.
> _______________________________________________
> Python-ideas mailing list
> Python-ideas at python.org
> http://mail.python.org/mailman/listinfo/python-ideas

Gerald Britton

More information about the Python-ideas mailing list