Allow heap removal at an arbitrary position, or a replacement with a new (or modified) object. · Issue #112498 · python/cpython (original) (raw)

Feature or enhancement

Proposal:

Currently, if an object on a heap is modified, it is necessary to run heapq.heapify() to restore the heap property.
As an example, take a priority queue with objects that have a priority propety.

removing an object from the heap

del heap[heap.index(myobj)] heapq.heapify(heap)

changing an object's priority

myobj.priority = new_priority heapq.heapify(heap)

Instead, it would be useful, if an object's index is known, to be able to remove, modify, or replace it in O(log n) time:

removing an object

heapq.heapremove(heap, heap.index(myobject))

updating its priority:

myobject.priority = new_priority i = heap.index(myobject) heapq.heapremove(heap, i, replacement=myobject)

While finding an object in the heap is a an O(n) operation, it need not invoke the all important __lt__ operator
and reordering a heap, when a single object changes, can be done with O(logN) comparisons.