> -----Original Message-----
> From: Python-Dev [mailto:python-dev-
> bounces+kristjan=ccpgames....@python.org] On Behalf Of Antoine Pitrou
> Sent: 27. mars 2014 15:53
> To: python-dev@python.org
> Subject: Re: [Python-Dev] collections.sortedtree
>
> On Thu, 27 Mar 2014 08:50:01 -0700
> Daniel Stutzbach <stutzb...@google.com> wrote:
> > To provide efficient cancellation and removal, a heap implementation
> > needs some way to efficiently answer "What is the current index of this
> item?".
> > There are a couple of ways to achieve that, but they all require more
> > storage than heapq's list-based approach.
>
> You are right. I was assuming the index is already known.
>
> Regards
>
> Antoine.
Yes. But for rare occurrances, it is annoying that heap.remove(item) is more
expensive than it
needs to be. It is a reasonable operation, just like list.remove() is.
I'll be willing to experiment with extending the heapq. methods to take an
optional "map" argument.
'map' would be a dict, mapping objects in the heap to indices. If provided,
each of the heapq methouds would
take care to update the map of any objects that it touches with the current
index of the object.
Usage could be something like:
heap = []
map = {}
def insert(i):
heapq.heappush(heap, I, map)
def pop(i):
return heapq.heappop(heap, map)
def remove(i):
heapq.heapdel(heap, map[i], map)
K
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
https://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
