Fibonacci queue is a bit special that insertion is constant but extraction is log.

A-star is very insertion heavy. In easy cases with a factor of 5, so using Fib gives significant boost in performance.