Implementare una coda con una coda a priorità

[davideddt]

Salve a tutti. Mi è stato chiesto di implementare una coda con una coda a priorità, qualcuno saprebbe darmi una mano perfavore?
Grazie

[andbin]

Originariamente inviato da davideddt
Salve a tutti. Mi è stato chiesto di implementare una coda con una coda a priorità, qualcuno saprebbe darmi una mano perfavore?

Praticamente, più o meno, quello che fa java.util.PriorityQueue. PriorityQueue è implementato con un "priority heap" e per stabilire l'ordine si basa su Comparable o Comparator.

Se devi implementare tu la coda da zero, e immagino per questioni "didattiche", non credo comunque che devi raggiungere simili livelli di complessità. Quello che si deve fare concettualmente è permettere di fare una es. insert(elemento) in modo tale che l'elemento si "disponga" nel posto giusto in modo che tutto sia nell'ordine tale per la priorità voluta.
Basterebbe anche solo usare un array o ArrayList in cui il punto di inserimento di un elemento è scelto usando l'algoritmo "binary search" (e nota, ci sono i binarySearch() di java.util.Arrays e java.util.Collections che sono di grande aiuto, se non devi farlo tu "a mano").

[davideddt]

innanzitutto grazie per la risposta. credo di non aver aver capito bene cosa hai detto.. Come hai dedotto mi è stato assegnato un esercizio (un vero e proprio progetto in realtà) che consiste nell'implementare una coda utilizzando una coda di priorità.. Questa è la consegna: "Implementare una coda con una coda a priorità". Grazie per l'aiuto.

[DonFrignolo]

Le code a priorità non sono altro che strutture dati dinamiche che permettono di gestire collezioni di oggetti, di processi, di roba.....
Le operazioni base sono:
inserimento
restituire il massimo elemento
cancellazione massimo elemento

In genere sono implementate tramite gli alberi binari o più precisamente con gli heap binari, ovvero alberi binari quasi completi con un ordinamento parziale, con la regola che il valore di un nodo figlio (successore) è minore o uguale a quello del nodo padre (predecessore).
Quindi ti basta implementare uno di questi alberi binari con le operazioni che ti ho descritto prima. Googla un po e vedrai che ne trovi un milione gia fatti. Poi se hai difficoltà posta pure che qualcuno che ti aiuta lo trovi.

[davideddt]

è possibile implementare una coda a priorità anche con una lista.. cosa è più conveniente? inoltre come potrei far si che la coda a priorità si comporti come una coda "semplice"?
Grazie mille per il vostro aiuto.

[andbin]

Originariamente inviato da davideddt
è possibile implementare una coda a priorità anche con una lista.. cosa è più conveniente?

Come è già stato detto, una "priority queue" implementata in modo "sofisticato" per essere ottimale, usa tipicamente un "heap" un tipo particolare di albero.
Ma se il tuo scopo è risolvere un esercizio (quindi qualcosa di "didattico") potrebbe anche andare bene una banale "lista", gestita però come ho detto sopra, cioè tenendo "ordinati" per priorità gli elementi inseriti.

Originariamente inviato da davideddt
inoltre come potrei far si che la coda a priorità si comporti come una coda "semplice"?

In che senso "semplice"??? Senza priorità? Se come struttura dati usi una lista, come ho detto, si potrebbe anche fare.

Una coda "normale" è FIFO, il primo che arriva è il primo che esce e da qui non si scappa. Se la coda invece è "a priorità", allora non è più FIFO in quanto gli elementi non escono necessariamente nell'ordine in cui sono entrati!!

Immagina lo stato di una coda a priorità, es.:

--> 5 8 10 22 -->

Dove a numero maggiore stabiliamo che corrisponde una priorità maggiore. Se inserisci un 15, non diventa:

--> 15 5 8 10 22 -->

ma

--> 5 8 10 15 22 -->

[davideddt]

Allora. so che una coda funziona con il principo first in first out e so che una coda di priorità, almeno per come mi è stata presentata, riceve degli oggetti chiamati entry costituiti da una chiave key e da un valore value. La coda a priorità mantiene le entry ordinate per valori delle key.
A questo punto l'esercizio assegnatomi consiste nell'implemetare una coda attraverso una coda a priorità: devo cioè far si che una coda a priorità funzioni come una coda ovvero rispetti il principio fifo.
Ovviamente in questo modo un utente "esterno" vedrà semplicemente una coda.

La coda a priorità mi è stata presentata attraverso un'implementazione mediante "sorted node list" che, volendo, è possibile trovare a questo indirizzo, al capitolo 8. Tuttavia il professore ha detto che "un certo livello di originalità" gli sarà gradito perciò, se la cosa fosse utile al fine della valutazione (che dipende anche dall'efficienza degli algoritmi ovviamente), potrei anche usare un heap, come mi hai suggerito.

Quindi la mia domanda è:
1) Mi è più conveninte utilizzare una lista o un heap per implementare la coda di priorità?
2) Come posso far si che la coda di priorità rispetti il principio FIFO?

[andbin]

Originariamente inviato da davideddt
riceve degli oggetti chiamati entry costituiti da una chiave key e da un valore value.

Nì (sì e no). In Java le collezioni sono collezioni di "oggetti" e un oggetto può avere una o più "proprietà". Che poi collezioni come PriorityQueue o TreeMap tengano "ordinata" la collezione, lo fanno semplicemente perché hanno anche una "nozione" sulla comparazione che (e ripeto sempre in Java) può essere stabilita tramite Comparable/Comparator la cui implementazione farà la comparazione su una o più proprietà dell'oggetto.

Quindi termini come key/value in questo caso vedili e usali in modo molto "astratto" e teorico. Gli oggetti non hanno chiavi/valori .... hanno proprietà. Che poi una o più proprietà vengano usate in un criterio di comparazione .... beh, ok.

Originariamente inviato da davideddt
devo cioè far si che una coda a priorità funzioni come una coda ovvero rispetti il principio fifo.

Questo in effetti non l'avevo capito bene (o comunque non l'avevi ben chiarito dall'inizio). Ma a questo punto .... che senso ha???

Originariamente inviato da davideddt
1) Mi è più conveninte utilizzare una lista o un heap per implementare la coda di priorità?

Scegli tu ... ovviamente l'heap è più complesso da gestire!

Originariamente inviato da davideddt
2) Come posso far si che la coda di priorità rispetti il principio FIFO?

Ecco ... è questo punto che mi lascia perplesso.
Facciamo un passo indietro. Immagina che tu debba usare java.util.PriorityQueue per fare una tua coda "fifo". PriorityQueue è a priorità ... non è fifo. La "nozione" di priorità non la puoi togliere, in quanto PriorityQueue si basa o sul natural ordering (Comparable) o su un ordinamento esterno (Comparator), uno dei due insomma e da qui non si scappa.

Ma se si volesse usare PriorityQueue come fifo?? Allora in teoria si dovrebbe implementare un criterio di comparazione specifico (Comparator) che "dica" che un oggetto inserito dopo ha priorità minore di uno inserito prima!!
Se si associasse un numero progressivo ad ogni oggetto inserito, si potrebbe fare.
Ma tutto questo .... avrebbe senso?

Ti è chiara la questione? Almeno per come la vedo io?

[davideddt]

si ho capito cosa dici e in effetti mi era venuto il dubbio che tu non avessi capito cosa devo fare io.
So che la cosa non ha molto senso: devi vederla come un esercizio didattico...

Per quanto riguarda la questione chiave/valore, mi è stato spiegato che:

"Coda di priorità è un insieme di coppie (chiave, valore) in cui la chiave svolge il ruolo di priorità associata al valore.
Una entry in una priority queue è una coppia (chiave, valore) che ha Metodi:

getKey(): ritorna la chiave dell’entry
getValue(): ritorna il valore associato all’entry

Interfaccia Java:
public interface Entry<K,V> {
public K key();
public V value();
}"

in sostanza una volta procuratami una coda di priorità devo farla funzionare come una coda.. come potrei fare quindi? grazie per l'aiuto/pazienza