template<typename Node, class HashFunc = HashTrait<Node>>
template<class Key, class Value>
class G3D::Pathfinder< Node, HashFunc >::PriorityQueue< Key, Value >
An inefficient implementation of a priority queue.
A heap data structure would make a more asymptotically efficient implementation at the cost of some implementation complexity. For short queues the difference is not significant, but for long queues the performance difference is O(n) vs. O(log n) for the removeMin operation. The advantage of this implementation is that we avoid complexity in the update() call, which must be backed by a hash table in any case for efficiency but which requires a more complex tree traversal if a heap is used.
Contents
