Heap (struttura dati): differenze tra le versioni

Versione delle 11:02, 24 apr 2018

Versione delle 18:53, 16 apr 2019

Riga 109:

L'heap ha diverse applicazioni:

*Algoritmi di ordinamento: l'[[heapsort]] è uno dei migliori metodi di ordinamento, essendo ''in-place'' e senza upper-bound quadratico.

*Algoritmi di selezione: un heap permette di accedere all'elemento con chiave minima o massima in tempo costante, e le altre selezioni (come la media o il k-esimo elemento) possono essere svolte in tempo sub-lineare.<ref>
{{Cita pubblicazione
|cognome= Frederickson
|nome= Greg N.

|contributo= An Optimal Algorithm for Selection in a Min-Heap

| doi = 10.1006/inco.1993.1030

|pp= 197–214

|lingua= en

Riga 119 ⟶ 122:

|numero= 2

|anno= 1993

|url= http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf}}</ref>

|accesso= 6 novembre 2015

|urlarchivio= https://web.archive.org/web/20121203045606/http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf

|dataarchivio= 3 dicembre 2012

|urlmorto= sì

}}

</ref>

*Algoritmi sui grafi: l'heap trova applicazione in svariati metodi, come l'[[algoritmo di Prim]] per la ricerca dell'[[albero ricoprente minimo]] o l'[[algoritmo di Dijkstra]] per la ricerca del [[cammino minimo]].

*Code di priorità: uno dei modi di implementare le [[Coda di priorità|code di priorità]] è tramite heap.