[New-bugs-announce] [issue35659] Add heapremove() function to heapq
report at bugs.python.org
Fri Jan 4 18:40:05 EST 2019
New submission from Wanja Chresta <wanja.chresta at gmail.com>:
Heap Queues are extremely useful data structures. They can, for example, be used to implement Dijkstra's algorithm for finding the shortest paths between nodes in a graph in O(edge * log vertices) time instead of (edge * vertices) without heaps.
One operation such implementations need, though, is the possibility to modify an element in the heap (and thus having to reorder it afterwards) in O(log n) time. One can model such an operation by removing a specific element from the heap and then adding the modified element.
So far, heapq only allows removing the first element through heappop; this is not what we need. Instead, we would want to support a heapremove function that removes an arbitrary element in the heap (if it exists) and raises ValueError if the value is not present.
list.remove cannot be used, since it needs O(n) time.
heapremove can be easily implemented by using bisect.bisect_left since heap is always sorted:
def heapremove(heap, x):
i = bisect.bisect_left(heap, x)
if heap[i] == x:
c.f. remove method in https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
components: Library (Lib)
nosy: Wanja Chresta
title: Add heapremove() function to heapq
versions: Python 3.8
Python tracker <report at bugs.python.org>
More information about the New-bugs-announce