### Abstract

The relaxed heap is a priority queue data structure that achieves the same amortized time bounds as the Fibonacci heap—a sequence of m decrease_key and n delete_min operations takes time O(m + n log n). A variant of relaxed heaps achieves similar bounds in the worst case—O(1) time for decrease_key and O(log n) for delete_min. Relaxed heaps give a processor-efficient parallel implementation of Dijkstra's shortest path algorithm, and hence other algorithms in network optimization. A relaxed heap is a type of binomial queue that allows heap order to be violated.

Original language | English (US) |
---|---|

Pages (from-to) | 1343-1354 |

Number of pages | 12 |

Journal | Communications of the ACM |

Volume | 31 |

Issue number | 11 |

DOIs | |

State | Published - Nov 1 1988 |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)

### Keywords

- Amortization
- parallel computation
- priority queue
- shortest paths
- worst-case hound

## Fingerprint Dive into the research topics of 'Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation'. Together they form a unique fingerprint.

## Cite this

Driscoll, J. R., Gabow, H. N., Shrairman, R., & Tarjan, R. E. (1988). Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation.

*Communications of the ACM*,*31*(11), 1343-1354. https://doi.org/10.1145/50087.50096