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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Recursive Star-Tree Parallel Data Structure
• Parallelism in Comparison Problems
• Optimal parallel selection has complexity O(log log N)
• Parallel selection
• Min-max heaps and generalized priority queues
• Building heaps in parallel
• Probabilistic Parallel Algorithms for Sorting and Selection
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (6)

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

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)