An optimal cache-oblivious priority queue and its application to graph algorithms

We develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and delete-min operations in O(1/B log _M/B 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 (cacheaware) 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.