Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation

James R. Driscoll, Harold N. Gabow, Ruth Shrairman, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

149 Scopus citations

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 languageEnglish (US)
Pages (from-to)1343-1354
Number of pages12
JournalCommunications of the ACM
Volume31
Issue number11
DOIs
StatePublished - Nov 1 1988

All Science Journal Classification (ASJC) codes

  • General Computer Science

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