Heap construction in the parallel comparison tree model

DOI10.1007/3-540-55706-7_13zbMATH Open1502.68094OpenAlexW1544402043MaRDI QIDQ5056136FDOQ5056136

Authors Paul F. Dietz

Publication date 9 December 2022

Published in Algorithm Theory — SWAT '92 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-55706-7_13

Mathematics Subject Classification ID

Randomized algorithms (68W20) Data structures (68P05) Parallel algorithms in computer science (68W10)

Recommendations

• Optimal parallel construction of heaps
• Building heaps in parallel
• Parallel heap operations on an EREW PRAM
• Heaps on Heaps
• Small-Rank Selection in Parallel, with Applications to Heap Construction

Cites work

• scientific article; zbMATH DE number 176748 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 742986 (Why is no real title available?)
• Building heaps in parallel
• Min-max heaps and generalized priority queues
• Optimal parallel selection has complexity O(log log N)
• Parallel selection
• Parallelism in Comparison Problems
• Probabilistic Parallel Algorithms for Sorting and Selection
• Recursive Star-Tree Parallel Data Structure

Cited in

(6)

• Comparator networks for binary heap construction
• Optimal parallel construction of heaps
• A note on constructing binary heaps with periodic networks.
• Comparator networks for binary heap construction
• Priority queues on parallel machines
• In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses

This page was built for publication: Heap construction in the parallel comparison tree model

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