Coda con priorità

Una coda con priorità memorizza sequenze di coppie (el, pr), con el un elemento e pr la priorità associata a quell’elemento.

La priorità massima dipende dal problema se è il valore minimo o massimo. (esame, data): priorità massima alla data minore (compito, compenso): priorità massima al compenso maggiore

Algoritmi

Dijkstra

Le coppie sono formate da (nodo, distanza dalla sorgente) e la priorità massima è il minor valore della distanza.

Prim

Le coppie sono formate da (arco, peso arco) e la priorità massima la ha il nodo con il peso minore.

Huffman

Le coppie sono formate da (insieme di caratteri, somma frequenze di occorrenza) e la priorità massima la ha il nodo con somma di frequenze minima.

Primitive

La massima priorità è associata al minimo valore di priorità.

1. makePriorityQueue(Q'): restituisce una coda che memorizza le coppie (el, pr) in Q’
2. isEmptyQueue(Q): ritorna true se la coda è vuota
3. enqueue(Q, el, pr): modifica la coda con inserimento coppia
4. minqueue(Q): ritorna l’elemento con priorità massima (valore minimo)
5. decreasePriority(Q, el, pr): modifica la coppia (el, pr') in coda aggiornando la priorità di elal nuovo valore pr < pr'
6. dequeue(Q): ritorna el con la massima priorità e elimina la coppia dalla coda

Ci sono tanti modi per realizzare questo concetto, utilizzando liste ordinate, liste non ordinate e min heap.

asd_23