Our great sponsors
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
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 10 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.
In this particular problem, all edge weights are 1..=9, so you can have a O(1) priority queue (fixed-bound bucket queue) if you make use of that fact.
(example: https://github.com/aldanor/aoc-2021/blob/master/src/day15/mo...)