Comparator networks for binary heap construction |
| |
Authors: | Gerth Stting Brodal M Cristina Pinotti |
| |
Affiliation: | Gerth Støting Brodal,M. Cristina Pinotti, |
| |
Abstract: | Comparator networks for constructing binary heaps of size n are presented which have size
and depth
. A lower bound of
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. |
| |
Keywords: | Binary heaps Comparator networks Selection networks Lower bounds |
本文献已被 ScienceDirect 等数据库收录! |