为何Boost堆在快速步进法中性能未优于std::multiset？

理论复杂度≠实际硬件表现 #

Fibonacci堆这类理论上O(1) amortized的decrease_key结构，在测试中表现拉胯，核心是CPU缓存友好性、常数因子开销和ARM架构特性的影响远超过理论复杂度优势：

• 缓存局部性碾压：预分配的二叉堆用连续数组存储，完美适配CPU缓存行预取机制，访问时缓存命中率接近100%；而Fibonacci堆、配对堆是指针链式结构，节点分散在内存各处，频繁的指针跳转触发大量缓存miss，M1 Max的大缓存也救不了随机访问的低效。
• 常数因子差距悬殊：Fibonacci堆的操作包含复杂的链表调整、标记剪枝逻辑，单次操作的常数开销远高于二叉堆简单的数组下标计算；std::multiset的红黑树实现经过工业级优化，分支预测对红黑树的路径判断适配更好，实际常数因子比Fibonacci堆小很多。
• ARM架构的针对性优化：M1 Max基于ARMv8.5-a，对连续内存的向量操作、预取优化支持极佳，但链式结构的指针操作完全没法利用这些特性；而且ARM加载/存储单元的随机访问延迟比x86更高，进一步放大了链式结构的劣势。

操作比例放大了实际开销 #

你的算法中decrease_key最多4n次，insert和extract_min各n次：

• 二叉堆的decrease_key虽然理论O(logn)，但连续内存的实际执行速度极快，4n次操作的总耗时反而比Fibonacci堆的“理论O(1)”更低——毕竟Fibonacci堆的O(1)是 amortized 平均，单次操作的复杂逻辑开销太高。
• std::multiset的删除重插虽然每次O(logn)，但红黑树的实际执行效率够高，和二叉堆的耗时差距很小，甚至在M1的优化下接近。

预分配内存的额外优势 #

你用的二叉堆是预分配内存，完全规避了动态内存分配的开销；而Boost的Fibonacci堆默认动态分配节点，频繁的内存申请释放会额外拖慢性能，这也是它表现不如二叉堆的一个小因素。

内容的提问来源于stack exchange，提问作者B0bby31