We present the Buffer Heap (BH), a cache-oblivious priority queue that supports Delete-Min, Delete, and Decrease-Key operations in O((1/B)log(N/B)) amortized block transfers from external memory, where B is the (unknown) block-size and N is the maximum number of elements in the queue. As is common in cache-oblivious algorithms, we assume a ‘tall cache’ (i.e., M = Ω(B^(1 + ε)), where M is the size of the main memory). We also assume the Decrease-Key operation only verifies that the element does not exist in the priority queue with a smaller key value, hence it also supports the insert operation in the same amortized bound. The amortized time bound for each operation is O(log N). We also present a Cache-Oblivious Tournament Tree (COTT), which is simpler than the Buffer Heap, but has weaker bounds.

Using the Buffer Heap we present cache-oblivious algorithms for undirected and directed single-source shortest path (SSSP) problems for graphs with non-negative edge-weights. On a graph with V vertices and E edges, our algorithm for the undirected case performs O(V + (E/B)log(V/B)) block transfers and for the directed case performs O((V + E/B)log(V/B)) block transfers. The running time of both algorithms is O((V + E)log V).

For both priority queues with Decrease-Key operation, and for shortest path problems on general graphs, our results appear to give the first non-trivial cache-oblivious bounds.