# Comparator Networks for Binary Heap Construction

Technical Report, MPI-I-98-1-002, Max-Planck-Institut für Informatik, 11 pages, January 1998.

## Abstract

Comparator networks for constructing binary heaps of size *n* are
presented which have size *O*(*n*loglog *n*) and depth *O*(log *n*). A
lower bound of *n*loglog *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.

**Online version**
mpi-i-98-1-002.pdf (205 Kb)

**BIBT**_{E}X entry

@techreport{mpi-i-98-1-002,
address = "Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany",
author = "Gerth St{\o}lting Brodal and M. Cristina Pinotti",
institution = "Max-Planck-Institut f{\"u}r Informatik",
month = "January",
number = "MPI-I-98-1-002",
pages = "11",
title = "Comparator Networks for Binary Heap Construction",
year = "1998"
}