Comparator networks for binary heap construction

DOI10.1016/S0304-3975(99)00137-1MaRDI QIDQ1589657zbMATH OpenWikidataFDO

Authors Gerth Stølting Brodal, Maria Cristina Pinotti

Publication date 12 December 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

binary heaps

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Comparator networks for binary heap construction
• A note on constructing binary heaps with periodic networks.
• scientific article; zbMATH DE number 742986
• Building heaps fast
• Heaps on Heaps

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 910857 (Why is no real title available?)
• scientific article; zbMATH DE number 3338920 (Why is no real title available?)
• A Method of Constructing Selection Networks with $O(\log n)$ Depth
• Finding the n-th largest element
• Finding the median
• Heap construction in the parallel comparison tree model
• Lower Bounds on Merging Networks
• Median selection requires \((2+\varepsilon)n\) comparisons
• Selection Networks
• Sorting in \(c \log n\) parallel steps
• The asymptotic complexity of merging networks
• Time bounds for selection

Cited in

(4)

• A note on constructing binary heaps with periodic networks.
• Comparator networks for binary heap construction
• Incremental encoding of pseudo-Boolean goal functions based on comparator networks
• Construction of halvers

This page was built for publication: Comparator networks for binary heap construction

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