Re:B-Heap vs. Binary Heap (2010)
by chucksmash on Sunday March 18, 2018 @10:57AM
(#16612218)
Do you have an article you would recommend on the route planning optimizations? That sounds interesting.
There’s a great recent-ish survey paper at https://arxiv.org/pdf/1504.05140.pdf which will give you pointers to papers in all directions :)
Nitpick, but your list-based LRU cache’s operations wouldn’t be in o(1) but rather O(1) – little oh means strictly slower growth, in this case sub-constant. Probably just a typo though. And it could be further optimised for locality by using a cyclic buffer instead of a linked list (-> no pointer chasing + sequential access), but see kilburn’s answer (the structure in the paper solves a different problem)