Code con priorità

Una entry è una coppia (chiave, valore) con chiave in un dominio $K$ e valore in $V$ (getKey(), getValue()).

Una coda con priorità (priority queue) è una collezione di entry le cui chiavi, non necessariamente distinte, rappresentano priorità e provengono da un universo totalmente ordinato. Ingressi e uscite si alternano in modo arbitrario, le priorità in ingresso non sono ordinate, le uscite avvengono in ordine di priorità.

interfaccia PriorityQueue<K,V>:
    size(), isEmpty()
    insert(k, v)   inserisce e restituisce la nuova entry (k, v)
    min()          restituisce una entry con chiave minima, senza toglierla
    removeMin()    restituisce e toglie una entry con chiave minima

Per convenzione chiave minima = priorità massima. Una coda basata sul massimo ha max() e removeMax() al posto di min() e removeMin().

Esempio

Partendo da una coda vuota:

L'ordine di inserimento è irrilevante per le uscite: contano solo le chiavi.

Applicazioni

Liste d'attesa (ad esempio negli aeroporti); scheduling di processi o di richieste di banda per la qualità del servizio; estrazione dei top-$k$ da una grande collezione di pattern; algoritmo di Dijkstra per i cammini minimi (vedi Cammini minimi e algoritmo di DijkstraGrafi pesati, lunghezza di un cammino e distanza; sottocammini di un cammino minimo; problema SSSP; algoritmo di Dijkstra con cloud e priority queue, rilassamento degli archi, esempio svolto; correttezza (due lemmi) e complessità O(min(n^2, (n+m) log n)) con lista non ordinata o heap; pesi non negativi.Cammini minimi e algoritmo di Dijkstra →); ordinamento (vedi sotto e Algoritmi di ordinamentoSelection sort e insertion sort (quadratici, con invarianti), merge sort (divide et impera, Theta(n log n)), quick sort (caso pessimo quadratico, medio n log n), heap sort (in loco, Theta(n log n)), ordinamento senza confronti per chiavi intere in un intervallo piccolo, limite inferiore Omega(n log n) per gli algoritmi basati su confronti.Algoritmi di ordinamento →).

Implementazione con liste

Le entry sono tenute in una lista doppiamente concatenata (vedi Liste, pile e codeRipasso degli ADT elementari: lista index-based (array) e position-based (lista doppiamente concatenata con sentinelle), pila LIFO, coda FIFO, deque, iteratori; interfacce, implementazioni e costi; array estendibile e coda circolare.Liste, pile e code →).

Lista non ordinata. insert: si aggiunge in coda, $\Theta(1)$. min: si scorre tutta la lista tenendo la chiave minore, $\Theta(n)$. removeMin: si trova il minimo e lo si toglie, $\Theta(n)$.

Lista ordinata (per chiave crescente). min e removeMin: si guarda/toglie il primo nodo, $\Theta(1)$. insert: si scorre fino alla prima chiave $\ge k$ e si inserisce prima di essa, $\Theta(n)$.

Le due liste spostano il costo da un'operazione all'altra; lo heap lo bilancia: nessuna operazione è lineare.

Ordinamento con una coda con priorità

Per ordinare $n$ chiavi: si fanno $n$ insert e poi $n$ removeMin, che restituiscono le chiavi in ordine crescente. Il costo dipende dall'implementazione:

• lista non ordinata: $n \cdot \Theta(1) + n \cdot \Theta(n) = \Theta(n^2)$ (è il selection sort);
• lista ordinata: $n \cdot \Theta(n) + n \cdot \Theta(1) = \Theta(n^2)$ (è l'insertion sort);
• heap: $n \cdot \Theta(\log n) + n \cdot \Theta(\log n) = \Theta(n \log n)$ (è l'heap sort).

Errori comuni

• Dimenticare che le chiavi possono ripetersi: removeMin restituisce una entry con chiave minima.
• Confondere "priorità massima" con "chiave massima": con la convenzione del corso la priorità massima è la chiave minima.
• Dire che min() e removeMin() hanno lo stesso costo in ogni implementazione: nello heap sono $\Theta(1)$ e $\Theta(\log n)$.