Code con priorità

Una entry è una coppia (chiave, valore) con chiave in un dominio $K$ e valore in $V$ (getKey(), getValue()). Come ogni ADT (Tipi di dato astrattiUn ADT è definito dalle operazioni e dal loro comportamento, non dalla rappresentazione; interfaccia e implementazione; realizzazione in Python con le classi e in C con header e tipo opaco; esempio di un ADT Frazione.Tipi di dato astratti →) la coda con priorità è definita dalle operazioni e non dall'implementazione.

Definizione (coda con priorità). 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 (due chiavi qualunque sono sempre confrontabili con $\le$, come per i numeri reali: Campi ordinati (Q e R)Gli assiomi di somma, prodotto e ordine comuni a Q e R, da cui derivano le regole di equazioni e disequazioni.Campi ordinati (Q e R) →). 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. Dopo insert(5,a), insert(2,b), insert(7,c), min() restituisce la entry con chiave $2$ e removeMin() la toglie.

Esempio

Partendo da una coda vuota:

L'ordine di inserimento è irrilevante per le uscite: contano solo le chiavi. Si noti la differenza con una coda FIFO (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 →): nella coda FIFO esce il primo arrivato, qui esce la chiave minima anche se è arrivata per ultima (la entry $(3,B)$ è stata inserita per terza ed è uscita per prima).

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 →).

Proprietà (code con priorità su liste: costi). 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)$.

Esempio. Con $n=1000$ entry, removeMin scorre fino a $1000$ entry in una lista non ordinata e ne guarda una sola in una lista ordinata. Nella lista ordinata insert(6, E) sul contenuto $(3,B)\ (5,A)\ (7,D)\ (9,C)$ confronta $6$ con $3$, $5$, $7$ e si ferma davanti a $7$ (prima chiave $\ge6$): il risultato è $(3,B)\ (5,A)\ (6,E)\ (7,D)\ (9,C)$, con fino a $n$ confronti nel caso peggiore (chiave maggiore di tutte).

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

Ordinamento con una coda con priorità

Proprietà (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).

Esempio. Con le chiavi $[5,2,7,1]$, quattro insert seguiti da quattro removeMin restituiscono $1,2,5,7$.

Da dove escono i conti. Con la lista non ordinata le $n$ removeMin scorrono liste di lunghezza $n, n-1, \dots, 1$, quindi il costo è $\sum_{k=1}^{n} k = \frac{n(n+1)}{2} \in \Theta(n^2)$ (somma dei primi interi: SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →). Con la lista ordinata le $n$ insert operano su liste lunghe $0, 1, \dots, n-1$ e costano al più $\sum_{k=0}^{n-1}(k+1) \in \Theta(n^2)$. Con lo heap l'$i$-esima operazione costa $O(\log i)$ e $\sum_{i=1}^{n}\log_2 i \le n\log_2 n$ (ogni addendo è al più $\log_2 n$, vedi Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →), quindi $O(n\log n)$. Il grafico confronta $n^2$ con $n \log_2 n$ (i due algoritmi quadratici contro heap sort, a meno di costanti):

Per $n$ piccolo l'heap può perdere (a $n=10$: $55$ contro $\approx 66$), perché le costanti contano: l'asintotica vale per $n$ grande (vedi Notazione asintoticaDefinizioni di O, Omega, Theta e o piccolo con le costanti c ed n0; esempi con costanti esplicite; proprietà (polinomi, esponenziali, logaritmi, somme, implicazioni tra notazioni); sommatorie notevoli; terminologia (logaritmica, lineare, polinomiale, esponenziale).Notazione asintotica →).

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)$.