An Adaptive Cache-Friendly Priority Queue: Fine-Tuning Heap Efficiency

A new approach to priority queues is presented, specifically designed to enhance cache-friendliness. Our data structure incorporates three adjustable parameters, allowing for a customized heap structure that can adapt to different system conditions. A search method is used, determining the optimal parameter values, eliminating the need for manual configuration and delivering notable performance improvements, as demonstrated through rigorous testing on the heap sort algorithm. Importantly, this designed data structure can dynamically grow without the need for reconstructing the heap tree.The adaptability of our cache-friendly priority queue makes it particularly interesting in the context of modern computing, where system architectures can vary widely.