Condivisione della tecnologia

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

mucchio

Heap e coda con priorità:

La coda con priorità è un tipo di dati astratto e l'heap è una struttura di dati, quindi l'heap non è una coda con priorità. L'heap è un modo per implementare una coda con priorità.
Esistono molti modi per implementare le code con priorità, come array ed elenchi collegati. Tuttavia, queste implementazioni possono garantire solo che una delle operazioni di inserimento ed eliminazione possa essere completata in complessità temporale O(1)O(1), mentre l'altra operazione deve essere completata in O(N)O(N) Completato entro il complessità temporale. L'heap può consentire il completamento dell'operazione di inserimento della coda di priorità entro la complessità temporale di O(log N)O(logN) e il completamento dell'operazione di eliminazione entro la complessità temporale di O(log N)O(logN). .

Un heap è uno speciale albero binario che soddisfa le seguenti condizioni:

1. Albero binario completo (i nodi sono disposti in ordine da sinistra a destra);
2. Il valore di ciascun nodo deve essere maggiore o uguale o inferiore o uguale al valore del relativo nodo figlio.

Caratteristiche dell'heap:

1. Gli elementi possono essere inseriti nell'heap con complessità temporale O(logN);
2. Gli elementi possono essere eliminati dall'heap con complessità temporale O(logN);
3. Il valore massimo o minimo nell'heap può essere ottenuto entro una complessità temporale O(1).

Classificazione dell'heap:

Heap massimo: il valore di ciascun nodo nell'heap è maggiore o uguale al valore del relativo nodo figlio. L'elemento superiore (nodo radice) dell'heap massimo è il valore massimo nell'heap.
Heap minimo: il valore di ciascun nodo nell'heap è inferiore o uguale al valore del relativo nodo figlio. L'elemento superiore (nodo radice) di un min-heap è il valore minimo nell'heap.
Il numero del nodo corrente è i, il numero del figlio sinistro è 2i e il numero del figlio destro è 2i+1.

Complessità temporale e complessità spaziale

Ordinamento dell'heap

Teoria: l'ordinamento dell'heap si riferisce all'utilizzo della struttura dei dati dell'heap per ordinare un insieme di elementi non ordinati.

I passaggi dell'algoritmo di ordinamento min-heap sono i seguenti:

Raccogli tutti gli elementi in un mucchio minimo;
Estrarre ed eliminare l'elemento superiore dell'heap e posizionare l'elemento superiore dell'heap nel set di dati T che memorizza gli elementi ordinati;
A questo punto, l'heap verrà adattato al nuovo heap minimo;
Ripetere i passaggi 3 e 4 finché non ci sono più elementi nell'heap;
A questo punto si ottiene un nuovo set di dati T, in cui gli elementi sono disposti in ordine dal piccolo al grande.

I passaggi dell'algoritmo di ordinamento dell'heap massimo sono i seguenti:

Raccogli tutti gli elementi in un mucchio massimo;
Estrarre ed eliminare l'elemento superiore dell'heap e posizionare l'elemento superiore dell'heap nel set di dati T che memorizza gli elementi ordinati;
A questo punto, l'heap verrà adattato al nuovo heap massimo;
Ripetere i passaggi 3 e 4 finché non ci sono più elementi nell'heap;
A questo punto si ottiene un nuovo set di dati T, in cui gli elementi sono disposti in ordine dal grande al piccolo.
Complessità temporale: O(Nlog N). N è il numero di elementi nell'heap.

Complessità spaziale: O(N). N è il numero di elementi nell'heap.