Comparator Networks for Binary Heap Construction

Gerth Stølting Brodal and M. Cristina Pinotti

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(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.

Online version

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

BIBT_EX entry

@techreport{mpi-i-98-1-002,
  address = "Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany",
  author = "Gerth Stø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"
}