Complessità del tempo di heapsort

L'ordinamento di heap, scritto come heapsort, è una sorta di algoritmo di smistamento. Impiega un elenco che è parzialmente ordinato e produce un elenco ordinato da esso. L'ordinamento può essere ascendente o scendendo. In questo articolo, l'ordinamento è ascendente. Si noti che heapsort non ordina un elenco incompleto non orientato. Ordina un elenco parzialmente ordinato (ordinato). Quell'elenco parzialmente ordinato è un mucchio. In questo articolo, l'heap considerato è il mucchio minimo (ascendente).

Un heap viene definito "parzialmente ordinato" e non "parzialmente ordinato". La parola "ordinamento" significa ordinare completo (ordinamento completo). Un heap non è parzialmente ordinato arbitrariamente. Un heap è parzialmente ordinato seguendo un criterio (modello), come mostrato di seguito.

Quindi, il centesimo è costituito da due fasi: costruire il mucchio ed estrarre l'elemento ordinato dalla parte superiore del mucchio. Nella seconda fase, dopo ogni estrazione, l'heap viene ricostruito. Ogni ricostruzione è più veloce del processo di costruzione originale poiché la ricostruzione viene eseguita da una build precedente, in cui un elemento è stato rimosso. E con ciò, Heapsort ordina un elenco completamente non ottimizzato.

Lo scopo di questo articolo è di spiegare brevemente heapsort e quindi produrre la sua complessità temporale (vedere il significato della complessità temporale di seguito). Verso la fine, la codifica viene eseguita in C++.

Heap minimo

Un mucchio può essere un mucchio minimo o un mucchio massimo. Un heap massimo è quello in cui il primo elemento è l'elemento più alto e l'intero albero o l'elenco corrispondente è parzialmente ordinato in ordine decrescente. Un minimo è quello in cui il primo elemento è il minimo elemento e l'intero elenco è parzialmente ordinato in ordine crescente. In questo articolo, viene considerato solo il mucchio minimo. Nota: nell'argomento dell'heap, un elemento è anche chiamato nodo.

Un heap è un albero binario completo. L'albero binario può essere espresso come un array (elenco); Leggi dall'alto verso il basso e da sinistra a destra. La proprietà heap per un minimo è che un nodo genitore è inferiore o uguale a ciascuno dei suoi due figli. Un esempio di un elenco non ordinato è:

9	19	24	5	3	11	14	22	7	6	17	15	nullo	nullo	nullo
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14

La prima riga di questa tabella è gli elementi dell'array. Nella seconda riga ci sono gli indici a base zero. Questo elenco di elementi può essere espresso come un albero. Gli elementi null sono stati aggiunti per creare un albero binario completo. A rigor di termini, gli elementi null non fanno parte dell'elenco (albero). Questo elenco non ha alcun ordine, quindi non è ancora un mucchio. Diventerà un mucchio quando ha avuto ordini parziali, secondo la proprietà heap.

Relazione tra nodi e indici

Ricorda, un heap è un albero binario completo prima di avere la configurazione heap (proprietà heap). L'elenco precedente non è ancora un mucchio, perché gli elementi non obbediscono alla proprietà del heap. Diventa un mucchio dopo aver riorganizzato elementi in ordine parziale secondo la proprietà Min-heap. L'ordine parziale può essere visto come un tipo parziale (anche se la parola "ordinamento" significa ordinazione completa).

Se un albero binario è un mucchio o no, ogni genitore ha due figli, tranne i nodi foglia (ultimo). C'è una relazione matematica tra gli indici tra ciascun genitore e i suoi figli. È il seguente: se il genitore è all'indice i, allora il figlio sinistro è all'indice:

2*i + 1

E il bambino giusto è all'indice:

2*i + 2

Questo è per indicizzazione basata su zero. E così, un genitore all'indice 0 ha il figlio sinistro all'indice 2 × 0+1 = 1 e il figlio destro a 2 × 0+2 = 2. Un genitore all'indice 1 ha il figlio sinistro all'indice 2 × 1+1 = 3 e figlio a destra all'indice 2 × 1+2 = 4; e così via.

Dalla proprietà Min-heap, un genitore a I è inferiore o uguale al figlio sinistro a 2i+1 e inferiore o uguale al figlio destro a 2i+2.

Mucchio

Heapifying significa costruire un mucchio. Significa riorganizzare gli elementi di un elenco (o un albero corrispondente) in modo che soddisfino la proprietà del heap. Alla fine del processo di heapifying, l'elenco o l'albero è un mucchio.

Se il precedente elenco non senza cortili è accumulato, diventerà:

3	5	11	7	6	15	14	22	9	19	17	24	nullo	nullo	nullo
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14

Nota: ci sono 12 elementi e non 15 nell'elenco. Nella seconda riga sono gli indici. Nel processo di costruzione del heap, gli elementi dovevano essere controllati e alcuni scambiati.

Si noti che il più piccolo e primo elemento è 3. Il resto degli elementi segue in modo ascendente ma ondulato. Se i bambini sinistra e destra nelle posizioni 2i+1 e 2i+2 sono ciascuno maggiore o uguale al genitore in I, allora questo è un minimo. Questo non è completo ordinamento o smistamento. Questo è un ordine parziale, secondo la proprietà heap. È da qui che inizia la fase successiva per l'ordinamento heap.

Accumulare complessità temporale

La complessità del tempo è il tempo di esecuzione relativo di qualche codice. Può essere visto come il numero di operazioni principali da completare. Esistono diversi algoritmi per la costruzione di heap. Il più efficiente e il più veloce dividi continuamente l'elenco per due, controllando gli elementi dal basso e quindi facendo un po 'di scambio di elementi. Sia N il numero di elementi pratici nell'elenco. Con questo algoritmo, il numero massimo di operazioni principali (scambio) è n. La complessità del tempo per l'angolo è data in precedenza come:

SU)

Dove n è n ed è il numero massimo possibile di operazioni principali. Questa notazione è chiamata Big-O Notation. Inizia con O in maiuscolo, seguito da parentesi. All'interno delle parentesi c'è l'espressione per il possibile numero più elevato di operazioni.

Ricorda: l'aggiunta può diventare moltiplicazione se la stessa cosa da aggiungere continua a ripetere.

Illustrazione del cumulo

Il precedente elenco non orientato verrà utilizzato per illustrare heapsort. L'elenco indicato è:

9 19 24 24 5 3 11 14 22 7 6 17 15

Il minimo prodotto dall'elenco è:

3 5 11 7 6 15 14 22 9 19 17 24 24

Il primo stadio di Heapsort è produrre il mucchio che è stato prodotto. Questo è un elenco parzialmente ordinato. Non è un elenco ordinato (completamente ordinato).

La seconda fase consiste nel rimuovere il minimo elemento, che è il primo elemento, dal mucchio, riesaminando il mucchio rimanente e rimuovendo i minimi elementi nei risultati. L'elemento minimo è sempre il primo elemento nel mucchio ri-heapified. Gli elementi non vengono rimossi e gettati via. Possono essere inviati a un array diverso nell'ordine in cui vengono rimossi.

Alla fine, il nuovo array avrebbe risolto tutti gli elementi (completamente), in ordine crescente; e non più solo parzialmente ordinato.

Nella seconda fase, la prima cosa da fare è rimuoverlo e posizionarlo nel nuovo array. I risultati sono:

3

E

5 11 7 6 15 14 22 9 19 17 24

Gli elementi rimanenti devono essere accumulati prima che venga estratto il primo elemento. Il mucchio degli elementi rimanenti può diventare:

5 6 7 9 15 14 22 11 19 17 24 24

L'estrazione di 5 e l'aggiunta al nuovo elenco (array) fornisce i risultati:

3 5

E

6 7 9 15 14 22 11 19 17 24 24

L'angolo del set rimanente darebbe:

6 7 9 15 14 22 11 19 17 24 24

L'estrazione di 6 e l'aggiunta al nuovo elenco (array) fornisce i risultati:

3 5 6

E

7 9 15 14 22 11 19 17 24 24

L'angolo del set rimanente darebbe:

7 9 11 14 22 15 19 17 24

L'estrazione di 7 e l'aggiunta al nuovo elenco fornisce i risultati:

3 5 6 7

E

9 11 14 14 22 15 19 17 24

L'angolo del set rimanente dà:

9 11 14 14 22 15 19 17 24

L'estrazione di 9 e l'aggiunta al nuovo elenco fornisce i risultati:

3 5 6 7 9

E

11 14 22 15 19 17 24 24

L'angolo del set rimanente dà:

11 14 17 15 19 22 24

L'estrazione di 11 e l'aggiunta al nuovo elenco fornisce i risultati:

3 5 6 7 9 11

E

14 17 15 19 22 24

L'angolo del set rimanente darebbe:

14 17 15 19 22 24

L'estrazione di 14 e l'aggiunta al nuovo elenco fornisce i risultati:

3 5 6 7 9 11 14

E

17 15 19 22 24

L'angolo del set rimanente darebbe:

15 17 19 22 24

L'estrazione di 15 e l'aggiunta al nuovo elenco fornisce i risultati:

3 5 6 7 9 11 14 15

E

17 19 22 24

L'angolo del set rimanente darebbe:

17 19 22 24

L'estrazione di 17 e l'aggiunta al nuovo elenco fornisce i risultati:

3 5 6 7 9 11 14 15 17 17

E

19 22 24

L'angolo del set rimanente darebbe:

19 22 24

L'estrazione di 19 e l'aggiunta al nuovo elenco fornisce i risultati:

3 5 6 7 9 11 14 15 17 19

E

22 24

L'angolo del set rimanente dà:

22 24

L'estrazione di 22 e l'aggiunta al nuovo elenco fornisce i risultati:

3 5 6 7 9 11 14 15 17 19 19 22

E

24

L'angolo del set rimanente dà:

24

L'estrazione di 24 e l'aggiunta al nuovo elenco fornisce i risultati:

3 5 6 7 9 11 14 15 17 19 22 24 24

E

- - -

L'array heap è ora vuoto. Tutti gli elementi che aveva all'inizio sono ora nel nuovo array (elenco) e ordinati.

Algoritmo di heapsort

Sebbene il lettore possa aver letto in libri di testo che Heapsort è costituito da due fasi, il cuscinetto può ancora essere visto come costituito da una fase, che si restringe iterativamente dall'array dato. Con ciò, l'algoritmo da ordinare con heapsort è il seguente:

• Accumulare l'elenco non preflitto.
• Estrai il primo elemento del heap e mettilo come primo elemento del nuovo elenco.
• Accumulare l'elenco rimanente.
• Estrai il primo elemento del nuovo heap e metti come l'elemento successivo del nuovo elenco.
• Ripeti i passaggi precedenti in ordine fino a quando l'elenco di heap è vuoto. Alla fine, il nuovo elenco è ordinato.

Complessità del tempo di heapsort corretta

L'approccio a una fase viene utilizzato per determinare la complessità del tempo per il heapsort. Supponiamo che ci siano 8 elementi non mobili da ordinare.

Il possibile numero massimo di operazioni per accumulare 8 elementi è 8.
Il possibile numero massimo di operazioni per accumulare 7 elementi rimanenti è 7.
Il possibile numero massimo di operazioni per accumulare i restanti 6 elementi è 6.
Il possibile numero massimo di operazioni per accumulare i restanti 5 elementi è 5.
Il possibile numero massimo di operazioni per accumulare i restanti 4 elementi è 4.
Il possibile numero massimo di operazioni per accumulare i restanti 3 elementi è 3.
Il possibile numero massimo di operazioni per accumulare i restanti 2 elementi è 2.
Il possibile numero massimo di operazioni per accumulare il restante 1 elemento è 1.

Il possibile numero massimo di operazioni è:

8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36

La media di questi numeri di operazioni è:

36 /8 = 4.5

Si noti che gli ultimi quattro cumuli nell'illustrazione precedente non sono cambiati, quando il primo elemento è stato rimosso. Alcuni dei precedenti cumuli non sono cambiati anche quando il primo elemento è stato rimosso. Con ciò, un numero medio migliore di operazioni principali (strollamenti) è 3 e non 4.5. Quindi, un numero medio totale migliore di operazioni principali è:

24 = 8 x 3
=> 24 = 8 x log₂8

Dal registro₂8 = 3.

In generale, la complessità del tempo medio per il heapsort è:

SU.log2n)

Laddove il punto significa moltiplicazione e n è n, il numero totale di elementi nell'elenco (entrambi gli elenco).

Si noti che il funzionamento dell'estrazione del primo elemento è stato ignorato. Sul tema della complessità del tempo, le operazioni che richiedono tempi relativamente brevi vengono ignorate.

Coding in c++

Nella libreria di algoritmo di C ++, c'è una funzione make_heap (). La sintassi è:

modello
costexpr void make_heap (randomecceccessiterator prima, casualcceccessiterator ultimo, confronta comp);

Prende l'iteratore che punta al primo elemento di un vettore come primo argomento e poi l'iteratore che punta appena oltre la fine del vettore come ultimo argomento. Per il precedente elenco non senza cortili, la sintassi verrebbe utilizzata come segue per ottenere un mucchio minimo:

vettore vtr = 9, 19, 24, 5, 3, 11, 14, 22, 7, 6, 17, 15;
vettore:: iterator iTerb = VTR.inizio();
vettore:: iteratore itere = vtr.FINE();
make_heap (iterb, itere, maggiore());

Questo codice modifica un contenuto vettoriale in una configurazione minima di heap. Nei seguenti vettori C ++, verranno utilizzati due vettori al posto di due array.

Per copiare e restituire il primo elemento di un vettore, utilizzare la sintassi vettoriale:

COSTEXPR RIFERIMENTO FRITTURA ();

Per rimuovere il primo elemento di un vettore e buttarlo via, usa la sintassi vettoriale:

CONSTEXPR iterator Erase (posizione const_iterator)

Per aggiungere un elemento sul retro di un vettore (elemento successivo), utilizzare la sintassi vettoriale:

costexpr void push_back (const t & x);

L'inizio del programma è:

#includere
#includere
#includere
Utilizzo dello spazio dei nomi std;

L'algoritmo e le librerie vettoriali sono inclusi. Il prossimo nel programma è la funzione heapsort (), che è:

vuoto heapsort (vettore & oldv, vettore & newv)
Se (oldv.size ()> 0)
vettore:: iterator iTerb = oldv.inizio();
vettore:: iteratore itere = oldv.FINE();
make_heap (iterb, itere, maggiore());
int next = oldv.davanti();
Oldv.cancella (iterb);
newv.push_back (Next);
heapsort (oldv, newv);

È una funzione ricorsiva. Utilizza la funzione make_heap () della libreria algoritmo C ++. Il secondo segmento di codice nella definizione della funzione estrae il primo elemento dal vecchio vettore dopo l'edificio heap e aggiunge come elemento successivo per il nuovo vettore. Si noti che nella definizione della funzione, i parametri vettoriali sono riferimenti, mentre la funzione viene chiamata con gli identificatori (nomi).

Una funzione principale C ++ adatta per questo è:

int main (int argc, char ** argv)

vettore oldv = 9, 19, 24, 5, 3, 11, 14, 22, 7, 6, 17, 15;
vettore newv;
heapsort (oldv, newv);
per (int i = 0; icout << newV[i] << ";

cout << endl;
restituzione 0;

L'output è:

3 5 6 7 9 11 14 15 17 19 22 24 24

ordinato (completamente).

Conclusione

L'articolo ha discusso in dettaglio la natura e la funzione dell'ordinamento di heap comunemente noto come heapsort, come un algoritmo di smistamento. La complessità del tempo di accantonamento, l'illustrazione di heapsort e il centesimo come algoritmo sono stati coperti e supportati da esempi. La complessità temporale media per un programma di heapsort ben scritto è O (Nlog (N))