Home → Magazine Archive → November 1988 (Vol. 31, No. 11) → Relaxed heaps: an alternative to Fibonacci heaps with... → Abstract

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

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

Communications of the ACM, Vol. 31 No. 11, Pages 1343-1354

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.

The full text of this article is premium content


No entries found