Author rajathagasthya
Recipients rajathagasthya, rhettinger, stutzbach
Date 2017-08-12.05:31:50
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1502515912.85.0.983303815097.issue31186@psf.upfronthosting.co.za>
In-reply-to
Content
I'd like to suggest a couple of utility methods for the heapq module which I think are useful:

1. heapfix() - Re-establishes heap invariant after item at 'any index' in the heap changes its value.

Currently, the way to fix the heap after an arbitrary item has changed is to just call heapify() on the entire heap. This is inefficient because heapify() tries to perform _siftup() operation on half of the items of the heap to maintain the heap invariant. Doing this is unnecessary because we know exactly which element (or index) was changed and became out of place. With a heapfix() function, we can just "fix" the heap from that position.

2. heapremove() - Removes an item at 'any index' from the heap and maintains heap invariant.

Pretty much same as above. If you remove an item from an arbitrary index, you have to call heapify() to restore the heap invariant.


Supporting these methods require minimal changes to the existing _siftup() and _siftdown() methods (basically just returning position values without changing any logic at all). I have a draft implementation which I've attached as a patch file here. If there's interest in this, I can write some tests and create a Github PR.

Thanks!
History
Date User Action Args
2017-08-12 05:31:53rajathagasthyasetrecipients: + rajathagasthya, rhettinger, stutzbach
2017-08-12 05:31:52rajathagasthyasetmessageid: <1502515912.85.0.983303815097.issue31186@psf.upfronthosting.co.za>
2017-08-12 05:31:52rajathagasthyalinkissue31186 messages
2017-08-12 05:31:51rajathagasthyacreate