[Python-ideas] Heap data type

[Gerald Britton]

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_
arguments.

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