Comparator networks for constructing binary heaps of size n are presented which have size View the MathML source and depth View the MathML source. A lower bound of View the MathML source 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.
Comparator Networks for Binary Heap Construction
PINOTTI, Maria Cristina
2001
Abstract
Comparator networks for constructing binary heaps of size n are presented which have size View the MathML source and depth View the MathML source. A lower bound of View the MathML source 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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
