article

Free access

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

Authors:

James R. Driscoll,

Harold N. Gabow,

Ruth Shrairman,

Robert E. TarjanAuthors Info & Claims

Communications of the ACM, Volume 31, Issue 11

Pages 1343 - 1354

https://doi.org/10.1145/50087.50096

Published: 01 November 1988 Publication History

PDF eReader

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.

References

[1]

Awerbuch, B. and Shiloach, Y. New connectivity and MSF algorithms for Ultracomputer and PRAM. In Proceedings of the IEEE 1983 International Conference on Parallel Processing (1983), pp. 175-179.

Google Scholar

[2]

Brown, M.R. Implementation and analysis of binomial queue algorithms. SIAM J. Comput. 7, 3 (1978), 298-319.

Crossref

Google Scholar

[3]

Fredman, M.L., and Tarjan, R.E. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 3 (1987), 596-615.

Digital Library

Google Scholar

[4]

Gabow, H.N. Scaling algorithms for network problems. J. Comp. and Sys. Sciences 31, 2 (1985), 148-168.

Digital Library

Google Scholar

[5]

Gabow, H.N., Galil, Z., Spencer, T.H:., and Tarjan, R.E. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combin,itorica 6, 2 (1986), 109-122.

Digital Library

Google Scholar

[6]

Gabow, H.N., and Tarjan, R.E. Almost-optimum speed-ups of algorithms for bipartite matching and related problems. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988, 514-527.

Digital Library

Google Scholar

[7]

Goldberg, A.V., and Tarjan, R.E. Solving minimum-cost flow problems by successive approximation. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, pp. 7-18; Math. of O.R., to appear.

Digital Library

Google Scholar

[8]

Kwan, S.C., and Ruzzo, W.L. Adaptive parallel algorithms for finding minimum spanning trees. In Proceedings of the IEEE 1984 International Conference on Parallel Processi,g, 1984, pp. 439-443.

Google Scholar

[9]

KruskaI, C.P., Rudolph, L., and Snir, M. Efficient parallel algorithms for graph problems. In Proceedings of the IEEE 1986 International Conference on Parallel Processing, 1986, pp. 869-876.

Google Scholar

[10]

Lawler, E.L. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, 1976.

Google Scholar

[11]

Orlin, J.B. A faster strongly polynomial minimum cost flow algorithm. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 377-387.

Digital Library

Google Scholar

[12]

Peterson, G.L. A balanced tree scheme for meldable heaps with updates. Tech. Rep. GIT-ICS-87-23, School of Information and Comp. Sci., Georgia Institute of Technology, Atlanta, Ga., 1987.

Google Scholar

[13]

Tarjan, R.E. Data Structures and Network Algorithms. SIAM, Philadelphia, Pa., 1983.

Digital Library

Google Scholar

[14]

Vuillemin, J. A data structure for manipulating priority queues. Commun. ACM 21, (1978), 309-314.

Digital Library

Google Scholar

Cited By

View all

Le CGopinathan KLee KGilbert SSergey I(2024)Concurrent Data Structures Made EasyProceedings of the ACM on Programming Languages10.1145/36897758:OOPSLA2(1814-1842)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689775
Willis PShenoy NHamilton JPan Y(2024)Resiliency in Networks Through Meshed Trees2024 15th International Conference on Network of the Future (NoF)10.1109/NoF62948.2024.10741359(45-53)Online publication date: 2-Oct-2024
https://doi.org/10.1109/NoF62948.2024.10741359
Stølting Brodal G(2024)Priority queues with decreasing keysTheoretical Computer Science10.1016/j.tcs.2024.1145631000:COnline publication date: 24-Jun-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114563
Show More Cited By

Index Terms

Recommendations

Toward Optimal Self-Adjusting Heaps

We give a variant of the pairing heaps that achieves the following amortized costs: O(1) per find-min and insert, O(log log n) per decrease-key and meld, O(log n) per delete-min; where n is the number of elements in the resulting heap on which the ...
Analysis of Self-Adjusting Heaps
Two-tier relaxed heaps

We introduce a data structure which provides efficient heap operations with respect to the number of element comparisons performed. Let n denote the size of the heap being manipulated. Our data structure guarantees the worst-case cost of O(1) for ...

Comments

Information & Contributors

Information

Published In

Communications of the ACM Volume 31, Issue 11

Nov. 1988

102 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/50087

Editor:
Peter J. Denning
NASA Ames Research Center, Moffett Field, CA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1988

Published in CACM Volume 31, Issue 11

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

153
Total Citations
View Citations
2,971
Total Downloads

Downloads (Last 12 months)373
Downloads (Last 6 weeks)58

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Le CGopinathan KLee KGilbert SSergey I(2024)Concurrent Data Structures Made EasyProceedings of the ACM on Programming Languages10.1145/36897758:OOPSLA2(1814-1842)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689775
Willis PShenoy NHamilton JPan Y(2024)Resiliency in Networks Through Meshed Trees2024 15th International Conference on Network of the Future (NoF)10.1109/NoF62948.2024.10741359(45-53)Online publication date: 2-Oct-2024
https://doi.org/10.1109/NoF62948.2024.10741359
Stølting Brodal G(2024)Priority queues with decreasing keysTheoretical Computer Science10.1016/j.tcs.2024.1145631000:COnline publication date: 24-Jun-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114563
Kawtikwar SNagi R(2024)HyLACJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104838187:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2024.104838
Cao NFineman JRussell KDhulipala LSun Y(2023)Efficient Construction of Directed Hopsets and Parallel Single-source Shortest Paths (Abstract)Proceedings of the 2023 ACM Workshop on Highlights of Parallel Computing10.1145/3597635.3598019(3-4)Online publication date: 18-Jul-2023
https://dl.acm.org/doi/10.1145/3597635.3598019
Duan RMao JShu XYin L(2023)A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00035(484-492)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00035
Cao NFineman JRussell KAgrawal KLee I(2022)Parallel Shortest Paths with Negative Edge WeightsProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538583(177-190)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538583
Potamias RNeofytou ABintsi KZafeiriou S(2022)GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)10.1109/CVPRW56347.2022.00335(2967-2976)Online publication date: Jun-2022
https://doi.org/10.1109/CVPRW56347.2022.00335
Satotani YMigita TTakahashi N(2022)An algorithm for updating betweenness centrality scores of all vertices in a graph upon deletion of a single edgeJournal of Complex Networks10.1093/comnet/cnac03310:4Online publication date: 8-Aug-2022
https://doi.org/10.1093/comnet/cnac033
Qiu LDong LGao YWang ZTan JJi Z(2022)An enhanced approach for joint configuration of a robot performing in a repetitive taskJournal of Manufacturing Systems10.1016/j.jmsy.2022.07.00964(454-467)Online publication date: Jul-2022
https://doi.org/10.1016/j.jmsy.2022.07.009
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Toward Optimal Self-Adjusting Heaps

Analysis of Self-Adjusting Heaps

Two-tier relaxed heaps

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations