[Python-Dev] collections.sortedtree (original) (raw)

Kristján Valur Jónsson kristjan at ccpgames.com
Fri Mar 28 10:20:35 CET 2014

-----Original Message----- From: Python-Dev [mailto:python-dev-_ _bounces+kristjan=ccpgames.com at python.org] On Behalf Of Antoine Pitrou Sent: 27. mars 2014 15:53 To: python-dev at python.org Subject: Re: [Python-Dev] collections.sortedtree

On Thu, 27 Mar 2014 08:50:01 -0700 Daniel Stutzbach <stutzbach at 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

More information about the Python-Dev mailing list