Comparator Networks for Binary Heap Construction

Gerth Stølting Brodal and M. Cristina Pinotti

In Theoretical Computer Science, volume 250(1-2), pages 235-245, 2001.

Abstract

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 notice

Copyright © 2000 by Elsevier Science B.V. All rights reserved.

Online version

tcs00.pdf (215 Kb)

DOI

10.1016/S0304-3975(99)00137-1

BIBTEX 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