[New-bugs-announce] [issue31186] Support heapfix() and heapremove() APIs in heapq module

[Rajath Agasthya]

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 <report at bugs.python.org>
<http://bugs.python.org/issue31186>
_______________________________________