Comparator networks for binary heap construction

Brodal, Gerth Stølting; Pinotti, M. Cristina

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

このアイテムの新しいバージョンが利用可能です:
https://pure.mpg.de/pubman/item/item_1819521_4

詳細要約

公開

報告書

Comparator networks for binary heap construction

MPS-Authors

/persons/resource/persons44187

Brodal, Gerth Stølting
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

1998-1-002
(全文テキスト（全般）), 10KB

付随資料 (公開)

There is no public supplementary material available

引用

Brodal, G. S., & Pinotti, M. C.(1998). Comparator networks for binary heap construction (MPI-I-1998-1-002). Saarbrücken: Max-Planck-Institut für Informatik.

引用: https://hdl.handle.net/11858/00-001M-0000-0014-9A0B-B

要旨

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 constructiion networks.