Cache-Oblivious Priority Queues with Decrease-Key and Applications to Graph Algorithms

John Iacono, Riko Jacob, Konstantinos Tsakalidis

We present priority queues in the cache-oblivious external memory model with block size $B$ and main memory size $M$ that support on $N$ elements, operation \textsc{UPDATE} (combin…