Implementazione di strutture dati per reti.

Si studia un'implementazione di code con priorità per le reti di confrontatori, uno tra i più semplici modelli paralleli. Le reti di confrontatori eseguono solo confronti fra dati, e tali confronti possono essere eseguiti in parallelo se non hanno dati in comune. Le reti più studiate sono le reti per la fusione, per l'ordinamento e per la selezione. In [A1], è proposta una rete ottima per la costruzione di uno heap. Essa richiede $O(n\log \log n)$ confrontatori per la costruzione di uno heap di dimensione $n$, ed ha profondità $O(\log n)$. È il primo esempio di rete di confrontatori che richiede un numero di confrontatori $c(n) \in \left (\Omega(n), o(n\log n) \right)$.