## Abstract

A priority queue is a fundamental data structure that maintains a dynamic set of (key, priority)-pairs and supports Insert, Delete, ExtractMin and DecreaseKey operations. In the external memory model, the current best priority queue supports each operation in amortized O(
_{B}
^{1} log
^{N}
_{B} ) I/Os. If the DecreaseKey operation does not need to be supported, one can design a more efficient data structure that supports the Insert, Delete and ExtractMin operations in O(
_{B}
^{1} log
^{N}
_{B} /log
^{M}
_{B} ) I/Os. A recent result shows that a degradation in performance is inevitable by proving a lower bound of Ω(
_{B}
^{1} log B/log log N) I/Os for priority queues with DecreaseKeys. In this paper we tighten the gap between the lower bound and the upper bound by proposing a new priority queue which supports the DecreaseKey operation and has an expected amortized I/O complexity of O(
_{B}
^{1} log
^{N}
_{B} /log log N). Our result improves the external memory priority queue with DecreaseKeys for the first time in over a decade, and also gives the fastest external memory single source shortest path algorithm.

Original language | English |
---|---|

Title of host publication | Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms |

Editors | Timothy M. Chan |

Number of pages | 13 |

Volume | PRDA19 |

Publisher | Society for Industrial and Applied Mathematics |

Publication date | 2019 |

Pages | 1331-1343 |

ISBN (Electronic) | 978-1-61197-548-2 |

Publication status | Published - 2019 |

Event | Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms - Westin San Diego , San Diego, United States Duration: 6 Jan 2019 → 9 Jan 2019 Conference number: 30 |

### Conference

Conference | Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Number | 30 |

Location | Westin San Diego |

Country/Territory | United States |

City | San Diego |

Period | 06/01/2019 → 09/01/2019 |