# Comparator Networks for Binary Heap Construction

In * Proc. 6th Scandinavian Workshop on Algorithm Theory*, volume 1432 of * Lecture Notes in Computer Science*, pages 158-168. Springer Verlag, Berlin, 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.

**Copyright notice**
© Springer-Verlag Berlin Heidelberg 1998. All rights reserved.

**Online version**

swat98cn.pdf (193 Kb)

**DOI**

10.1007/BFb0054364

**Links**

**Slides**

swat98cn.pdf (146 Kb)

**BIBT**_{E}X entry

@incollection{swat98cn,
author = "Gerth St{\o}lting Brodal and M. Cristina Pinotti",
booktitle = "Proc. 6th Scandinavian Workshop on Algorithm Theory",
doi = "10.1007/BFb0054364",
isbn = "978-3-540-64682-2",
pages = "158-168",
publisher = "Springer {V}erlag, Berlin",
series = "Lecture Notes in Computer Science",
title = "Comparator Networks for Binary Heap Construction",
volume = "1432",
year = "1998"
}