In Theoretical Computer Science, volume 250(1-2), pages 235-245, 2001.
Comparator networks for constructing binary heaps of size n are presented which have size O(nloglog n) and depth O(log n). A lower bound of nloglog n-O(n) for the size of any heap construction network is also proven, implying that the networks presented are within a constant factor of optimal. We give a tight relation between the leading constants in the size of selection networks and in the size of heap construction networks.
Copyright noticeCopyright © 2000 by Elsevier Science B.V. All rights reserved.
Online version
tcs00.pdf (215 Kb)
DOI
BIBT_{E}X entry
@article{tcs00, author = "Gerth St{\o}lting Brodal and M. Cristina Pinotti", doi = "10.1016/S0304-3975(99)00137-1", issn = "0304-3975", journal = "Theoretical Computer Science", number = "1-2", pages = "235-245", title = "Comparator Networks for Binary Heap Construction", volume = "250", year = "2001" }
Other versions