Coda di priorità
.mw-parser-output .avviso .mbox-text-div>div,.mw-parser-output .avviso .mbox-text-full-div>div{font-size:90%}.mw-parser-output .avviso .mbox-image div{width:52px}.mw-parser-output .avviso .mbox-text-full-div .hide-when-compact{display:block}
Nella teoria delle code, una coda di priorità è una struttura dati astratta, simile ad una coda o ad una pila, ma diversa da queste in quanto ogni elemento inserito all'interno della coda possiede una sua "priorità". In una coda di priorità, ogni elemento avente priorità più alta, viene inserito prima rispetto ad un elemento avente priorità più bassa. In particolare, l'elemento con priorità più alta si trova in testa alla coda, quello con priorità più bassa si troverà, appunto, in coda.
Indice
1 Operazioni
2 Implementazione
3 Applicazioni
4 Relazione tra coda di priorità ed algoritmi di ricerca
5 Note
6 Bibliografia
Operazioni |
Le code di priorità devono, necessariamente, supportare tali operazioni:
- insert(elemento e, chiave k): Tale operazione inserisce l'elemento e nella coda in base alla sua priorità definita dalla chiave k.
- findMin(): Tale operazione restituisce l'elemento della coda avente priorità più bassa, senza eliminarlo.
- removeMin(): Tale operazione elimina l'elemento della coda avente priorità più bassa.
- findMax(): Tale operazione restituisce l'elemento della coda avente priorità più alta, senza eliminarlo.
- removeMax(): Tale operazione restituisce l'elemento della coda avente priorità più alta.
Implementazione |
Per implementare una coda di priorità viene spesso utilizzato l'heap binario in quanto, tale struttura, permette l'inserimento e l'eliminazione in un tempo di O(logn) nel caso peggiore. È possibile anche utilizzare heap binomiali o heap di Fibonacci per rendere più efficaci determinate operazioni.[1] Per via della naturale implementazione delle code di priorità con gli heap queste spesso vengono chiamate in letteratura anche heap rovesciato. Intendendo con heap rovesciato uno heap che ha nella radice l'elemento minore dell'albero, e non il maggiore, e nel quale ogni figlio è maggiore del padre cioè al contrario di uno heap standard.
Applicazioni |
Le code a priorità vengono largamente impiegate in informatica e in generale nell'ambito dell'elaborazione di dati (comprese le telecomunicazioni e i circuiti elettronici digitali) per eseguire operazioni complesse quali:
- ordinamento di elementi sulla base della loro priorità
- ottimizzazioni nell'accesso a risorse condivise, soprattutto in caso di accessi concorrenti e in congestione
- gestione di attività a schedulazione
algoritmi euristici di ricerca
Relazione tra coda di priorità ed algoritmi di ricerca |
Una coda di priorità viene spesso accoppiata agli algoritmi di ricerca. Nella seguente tabella, per ogni algoritmo, viene indicato l'implementazione migliore e i vari costi:
| Algoritmo | Implementazione con code di priorità | Caso migliore | Caso medio | Caso peggiore |
|---|---|---|---|---|
Smoothsort | Heap di Leonardo | n{displaystyle n}  | nlog(n){displaystyle nlog(n)}  | nlog(n){displaystyle nlog(n)} |
Selection sort | Array non ordinato | n2{displaystyle n^{2}}  | n2{displaystyle n^{2}} | n2{displaystyle n^{2}} |
Insertion Sort | Array ordinato | n{displaystyle n} | n2{displaystyle n^{2}} | n2{displaystyle n^{2}} |
Tree sort | Albero binario di ricerca | nlog(n){displaystyle nlog(n)} | nlog(n){displaystyle nlog(n)} | nlog(n){displaystyle nlog(n)} |
Heapsort | Heap | nlog(n){displaystyle nlog(n)} | nlog(n){displaystyle nlog(n)} | nlog(n){displaystyle nlog(n)} |
Note |
^ (EN) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, Chapter 20: Fibonacci Heaps, in Introduction to Algorithms, MIT Press and McGraw-Hill, 2001, pp. 476–497, 518, ISBN 0-262-03293-7.
Bibliografia |
- Camil Demetrescu, Irene Finocchi, Giuseppe Italiano, Algoritmi e strutture dati, McGraw-Hill, 2004. ISBN 88-386-6161-8. Capitolo 8: Code di priorità, pp.187-206.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001
.mw-parser-output .navbox{border:1px solid #aaa;clear:both;margin:auto;padding:2px;width:100%}.mw-parser-output .navbox th{padding-left:1em;padding-right:1em;text-align:center}.mw-parser-output .navbox>tbody>tr:first-child>th{background:#ccf;font-size:90%;width:100%}.mw-parser-output .navbox_navbar{float:left;margin:0;padding:0 10px 0 0;text-align:left;width:6em}.mw-parser-output .navbox_title{font-size:110%}.mw-parser-output .navbox_abovebelow{background:#ddf;font-size:90%;font-weight:normal}.mw-parser-output .navbox_group{background:#ddf;font-size:90%;padding:0 10px;white-space:nowrap}.mw-parser-output .navbox_list{font-size:90%;width:100%}.mw-parser-output .navbox_odd{background:#fdfdfd}.mw-parser-output .navbox_even{background:#f7f7f7}.mw-parser-output .navbox_center{text-align:center}.mw-parser-output .navbox .navbox_image{padding-left:7px;vertical-align:middle;width:0}.mw-parser-output .navbox+.navbox{margin-top:-1px}.mw-parser-output .navbox .mw-collapsible-toggle{font-weight:normal;text-align:right;width:7em}.mw-parser-output .subnavbox{margin:-3px;width:100%}.mw-parser-output .subnavbox_group{background:#ddf;padding:0 10px}
Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica
