An Optimal Cache‐Oblivious Priority Queue and Its Application to Graph Algorithms
Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland‐Minkley, J. Ian Munro · SIAM Journal on Computing · 2007
We develop an optimal cache‐oblivious priority queue data structure, supporting insertion, deletion, and delete‐min operations in $O(\frac{1}{B}\log_{M/B}\frac{N}{B})$ amortized memory transfers, where M and B are the memory and block transfer sizes of any two consecutive levels of a multilevel memory hierarchy. In a cache‐oblivious data structure, M and B are not used in the description of the structure. Our structure is as efficient as several previously developed external memory (cache‐aware) priority queue data structures, which all rely crucially on knowledge about M and B. Priority queues are a critical component in many of the best known external memory graph algorithms, and using our cache‐oblivious priority queue we develop several cache‐oblivious graph algorithms.