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

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