The cache oblivious model of computation is a two-level memory model with the assumption that the parameters of the model are unknown to the algorithms. A consequence of this assumption is that an algorithm efficient in the cache oblivious model is automatically efficient in a multi-level memory model. Arge et al. recently presented the first optimal cache oblivious priority queue, and demonstrated the importance of this result by providing the first cache oblivious algorithms for graph problems. Their structure uses cache oblivious sorting and selection as subroutines. In this paper, we devise an alternative optimal cache oblivious priority queue based only on binary merging. We also show that our structure can be made adaptive to different usage profiles.
Lecture Notes in Computer Science: 13th International Symposium, Isaac 2002 Vancouver, Bc, Canada, November 21–23, 2002 Proceedings, 2002, p. 219-228
Binary tree; Data structure; Subroutine; Queue; Priority; Adaptive method
Main Research Area:
Lecture Notes in Computer Science
International Symposium on Algorithms and Computation, 2002