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.


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:

Python tracker <>
Python-bugs-list mailing list

Reply via email to