[Python-Dev] collections.sortedtree

[Kristján Valur Jónsson]

> -----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