Brodal G., Pinotti M. C. Comparator networks for binary heap construction. In: Algorithm Theory - SWAT'98. 6th Scandinavian Workshop on Algorithm Theory (Stockholm, Sweden, July, 8-10 1998). Proceedings, pp. 158 - 168. S. Arnborg, L. Ivansson (Eds.) (eds.). (Lecture Notes in Computer Science, vol. 1432). Springer, 1998. |

Abstract (English) |
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. | |

Subject | Data structures C.3 special purpose and application based systems E.1 Data Structures |

1) Download Document PDF |

Open access Restricted Private