[Boost-users] heap handle invalidation

Subject: [Boost-users] heap handle invalidation
From: 谢任中 (joshchia_at_[hidden])
Date: 2013-04-18 22:17:42

Hi,

I'm using a mutable heap, in particular a mutable d_ary_heap, for the
priority queue in Djikstra's algorithm.

When does a handle become invalid? I don't know how a d_ary_heap is
implemented, but if it's like the standard array-backed binary heap, then I
would expect invalidation of many handles whenever an item gets popped or
an item gets increased or decreased.

I need references to the elements in order to update them, so if the
invalidation I expect does happen as I describe, how can I get permanent
references/pointers/iterators to the elements? Perhaps another
implementation besides d_ary_heap? Although I haven't profiled the
performance, I think even though something like the fibonacci heap may have
permanent handles, pointer chasing, more frequent cache misses and frequent
dynamic memory allocation may be detrimental to performance.

Which heap implementation supports key increase without handle invalidation?

Josh