| Comparator Networks for Binary Heap Construction (2000) | |||||||||||||||||
Abstract | |||||||||||||||||
| 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. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||