Refined complexity analysis for heap operations

DOI10.1016/0022-0000(87)90016-XMaRDI QIDQ578912zbMATH OpenOpenAlexFDO

Authors Michael L. Fredman, Thomas H. Spencer

Publication date 1987

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(87)90016-x

zbMATH Keywords

data structureheappriority queuefrequency of findmin operationsinherent complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Recommendations

• Heaps on Heaps
• Optimizing binary heaps
• scientific article; zbMATH DE number 742986
• Two-tier relaxed heaps
• Algorithm Theory - SWAT 2004

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• A data structure for manipulating priority queues
• Finding Minimum Spanning Trees
• Time bounds for selection

Cited in

(11)

• scientific article; zbMATH DE number 1953023 (Why is no real title available?)
• Recurrence relations on heaps
• Optimal Parallel Algorithms For Multiselection On Mesh-Connected Computers
• Available stabilizing heaps
• Heaps on Heaps
• On computing an optimal permutation of ranks for multiselection
• In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses
• scientific article; zbMATH DE number 1543353 (Why is no real title available?)
• Optimizing binary heaps
• Stacks, queues, and deques with order-statistic operations
• The amortized complexity of Henriksen's algorithm

This page was built for publication: Refined complexity analysis for heap operations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q578912)