Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation
- 1 November 1988
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 31 (11) , 1343-1354
- https://doi.org/10.1145/50087.50096
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.Keywords
This publication has 9 references indexed in Scilit:
- A faster strongly polynomial minimum cost flow algorithmPublished by Association for Computing Machinery (ACM) ,1988
- Almost-optimum speed-ups of algorithms for bipartite matching and related problemsPublished by Association for Computing Machinery (ACM) ,1988
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Solving minimum-cost flow problems by successive approximationPublished by Association for Computing Machinery (ACM) ,1987
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphsCombinatorica, 1986
- Scaling algorithms for network problemsJournal of Computer and System Sciences, 1985
- Data Structures and Network AlgorithmsPublished by Society for Industrial & Applied Mathematics (SIAM) ,1983
- Implementation and Analysis of Binomial Queue AlgorithmsSIAM Journal on Computing, 1978
- A data structure for manipulating priority queuesCommunications of the ACM, 1978