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 b

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.