[Python-Dev] collections.sortedtree
Daniel Stutzbach
stutzbach at google.com
Thu Mar 27 16:50:01 CET 2014
On Wed, Mar 26, 2014 at 3:02 PM, Antoine Pitrou <solipsis at pitrou.net> wrote:
>
> Ideally, I think you should be able to replace the cancelled item with
> the last item in the heap and then fix the heap in logarithmic time,
> but the heapq API doesn't seem to provide a way to do this.
Due to way the heapq is implemented, it can't provide an efficient API for
removing an arbitrary item. Swapping with the last element allows you to
efficiently remove the item at a particular index, but you first need to
find the current index of an item, which requires a O(n) scan.
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.
--
Daniel Stutzbach
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20140327/ea3ef497/attachment-0001.html>
More information about the Python-Dev
mailing list