Yes, though sometimes it is possible to replace a fully general priority queue with a faster structure that is using the structure of the problem at hand. For example, this problem (AoC day 15) has only ever a count of unique priorities that is 11 or fewer. That allows a queue implementation to be https://github.com/yxhuvud/aoc21/blob/main/day15.cr#L27-L51 , being amortized O(1) in both insertion and deletion. This pushed down the runtime another magnitude for me, the whole day running at 0.014s.

IntMaps in Haskell actually have time complexity of O(min(n,W))[0] = O(1) for this problem, for insertion and getting the minimal element where n is the number of entries in the map (which is 9 here) and W is the word size in bits. Another way to think of it is it's just a fixed-length array where the entries are lists of vertices.

[0] https://hackage.haskell.org/package/containers-0.6.5.1/docs/...

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.