For now, we initialize a new weighted node in the A* algorithms for each leaving edge and put it in the priority queue, although it is already in the queue. This implementation is no problem regarding functionality (you just need the node with less weight), but it needs unused memory in case your nodes are weighted multiple times.
Solution: A priority queue with complexity o(n) (less than linear!) for contains could remove an existing node fast. Returning it, modifying and putting it back to the queue in O(logn) would do the same functionality without a new initialization. contains in o(n) could be done by using a hash map mapping an element on its position in the queue.
For now, we initialize a new
weighted nodein the A* algorithms for each leaving edge and put it in the priority queue, although it is already in the queue. This implementation is no problem regarding functionality (you just need the node with less weight), but it needs unused memory in case your nodes are weighted multiple times.Solution: A priority queue with complexity o(n) (less than linear!) for
containscould remove an existing node fast. Returning it, modifying and putting it back to the queue in O(logn) would do the same functionality without a new initialization.containsin o(n) could be done by using a hash map mapping an element on its position in the queue.