Editing A* search algorithm (section)

===Implementation details===
There are a number of simple optimizations or implementation details that can significantly affect the performance of an A* implementation.  The first detail to note is that the way the priority queue handles ties can have a significant effect on performance in some situations.  If ties are broken so the queue behaves in a [[LIFO (computing)|LIFO]] manner, A* will behave like [[depth-first search]] among equal cost paths (avoiding exploring more than one equally optimal solution).

When a path is required at the end of the search, it is common to keep with each node a reference to that node's parent.  At the end of the search, these references can be used to recover the optimal path.  If these references are being kept then it can be important that the same node doesn't appear in the priority queue more than once (each entry corresponding to a different path to the node, and each with a different cost).  A standard approach here is to check if a node about to be added already appears in the priority queue.  If it does, then the priority and parent pointers are changed to correspond to the lower-cost path. A standard [[binary heap]] based priority queue does not directly support the operation of searching for one of its elements, but it can be augmented with a [[hash table]] that maps elements to their position in the heap, allowing this decrease-priority operation to be performed in logarithmic time. Alternatively, a [[Fibonacci heap]] can perform the same decrease-priority operations in constant [[amortized time]].