Comparator Networks for Binary Heap Construction

Gerth Stølting Brodal and M. Cristina Pinotti

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

© Springer-Verlag Berlin Heidelberg 1998. All rights reserved.

Online version

swat98cn.pdf (193 Kb)

DOI

10.1007/BFb0054364

Links

• Springer Verlag
• Lecture Notes in Computer Science

Slides

swat98cn.pdf (146 Kb)

BIBT_EX entry

@incollection{swat98cn,
  author = "Gerth Stø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"
}