# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Comparator Networks for Binary Heap Construction

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Brodal, G. S., & Pinotti, M. C. (1998). Comparator Networks for Binary Heap Construction.
In S. Arnborg, & L. Ivansson (*Proceedings of the
6th Scandinavian Workshop on Algorithm Theory (SWAT-98)* (pp. 158-168). Berlin, Germany: Springer.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-3773-B

##### 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 construction networks.