Comparator networks for constructing binary heaps of size n are presented which have size O(nloglogn) and depth O(logn). A lower bound of nloglogn-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.
Comparator networks for binary heap construction
2000
Abstract
Comparator networks for constructing binary heaps of size n are presented which have size O(nloglogn) and depth O(logn). A lower bound of nloglogn-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.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
prod_406107-doc_141980.pdf
solo utenti autorizzati
Descrizione: Comparator networks for binary heap construction
Tipologia:
Versione Editoriale (PDF)
Dimensione
129.68 kB
Formato
Adobe PDF
|
129.68 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
