New submission from Rajath Agasthya: 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! ---------- components: Library (Lib) files: heapq_fix_remove.patch keywords: patch messages: 300190 nosy: rajathagasthya, rhettinger, stutzbach priority: normal severity: normal status: open title: Support heapfix() and heapremove() APIs in heapq module type: enhancement versions: Python 3.7 Added file: http://bugs.python.org/file47079/heapq_fix_remove.patch _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue31186> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
