@techreport{BrodalPinotti98,
TITLE = {Comparator networks for binary heap construction},
AUTHOR = {Brodal, Gerth St{\o}lting and Pinotti, M. Cristina},
LANGUAGE = {eng},
NUMBER = {MPI-I-1998-1-002},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Saarbr{\"u}cken},
YEAR = {1998},
DATE = {1998},
ABSTRACT = {Comparator networks for constructing binary heaps of size $n$ are presented which have size $O(n\log\log n)$ and depth $O(\log n)$. A lower bound of $n\log\log 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 constructiion networks.},
TYPE = {Research Report / Max-Planck-Institut für Informatik},
}