Cache optimizing a priority queue

A deep dive into cache-optimizing a priority queue in C++ by replacing the standard binary heap with a B-heap (heap of mini-heaps). The post explains how standard binary heaps suffer from poor cache utilization at scale, then explores the B-heap approach where mini-heaps are sized to fit cache lines. Several implementation variants are benchmarked: a plain int B-heap, a B-heap holding pairs with unique_ptr, a split structure separating priorities from pointers, and finally using integer indexes instead of pointers. Results show consistent speedups over std::priority_queue, especially when separating priority data from associated values. Source code is available on GitHub.