非表示:
キーワード:
-
要旨:
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.
