Was shocked to find that Python's heapq module does not have a way to find (in constant time) or delete or update values. So I developed priorityq to provide these missing features and much more.
The short answer is that I decoupled the actual heap storage from the PQ api that uses the heap storage so that I keep a map of values to handles (as returned by the storage).
Consider the python heapq module. It directly works on a list, maintaining the heap invariant. So you (the dev) can freely modify the underlying list invalidating the heap invariant. But if the (heap) storage returned handle objects that encapsulated the position within the heap, then the client can just update the priority of the value pointed by the handle without knowing anything about how the heap is implemented.
So linear increase in memory usage (for the map) but fast retrievals. I plan to try this out with other kinds of heap implementations soon.
3 comments
[ 1.6 ms ] story [ 18.8 ms ] threadWould love to get some feedback.
Consider the python heapq module. It directly works on a list, maintaining the heap invariant. So you (the dev) can freely modify the underlying list invalidating the heap invariant. But if the (heap) storage returned handle objects that encapsulated the position within the heap, then the client can just update the priority of the value pointed by the handle without knowing anything about how the heap is implemented.
So linear increase in memory usage (for the map) but fast retrievals. I plan to try this out with other kinds of heap implementations soon.