Tutorial della struttura dei dati heap

I dati sono un insieme di valori. I dati possono essere raccolti e messi in riga, o in una colonna o in una tabella o sotto forma di un albero. La struttura dei dati non è solo il posizionamento dei dati in una di queste forme. Nel calcolo, la struttura dei dati è uno di questi formati, oltre alla relazione tra i valori, più le operazioni (funzioni) funzionano sui valori. Dovresti già avere una conoscenza di base sulla struttura dei dati degli alberi prima di venire qui, come concetti lì, verranno usati qui con poca o nessuna spiegazione. Se non hai questa conoscenza, leggi il tutorial intitolato, Tutorial della struttura dei dati degli alberi per principianti, al link, https: // linuxhint.com/albero_data_structure_tutorial_beginners/. Dopodiché, continua a leggere questo tutorial.Una struttura di dati heap è un albero binario completo o quasi completo, in cui il figlio di ciascun nodo è pari o inferiore di valore rispetto al valore del suo genitore. In alternativa, è un tale albero in cui il valore di un genitore è uguale o inferiore al valore di uno dei suoi figli. Il valore (dato) di un albero è anche chiamato chiave.

Illustrazione delle strutture di dati heap

Esistono due tipi di cumuli: un heap massimo e un minimo. Una struttura massima-heap è dove il valore massimo è la radice e i valori diventano più piccoli man mano che l'albero scende; Qualsiasi genitore è pari o più grande di valore rispetto ai suoi figli immediati. Una struttura a taglio minimo è dove il valore minimo è la radice e i valori diventano più grandi man mano che l'albero scende; Qualsiasi genitore è pari o inferiore di valore rispetto a uno dei suoi figli immediati. Nei seguenti diagrammi, il primo è un heap massimo e il secondo è un minimo:

Per entrambi i cumuli, nota che per una coppia di bambini, non importa se quello a sinistra sia il valore maggiore. Una riga in un livello nell'albero, non deve necessariamente essere riempita dal minimo al massimo, da sinistra; non è anche necessariamente riempito dal massimo al minimo, da sinistra.

Che rappresenta un mucchio in un array

Affinché il software possa utilizzare facilmente un heap, il mucchio deve essere rappresentato in un array. Il capannone massimo sopra, rappresentato in un array è:

89, 85, 87, 84, 82, 79, 73, 80, 81 ,,, 65, 69

Questo viene fatto a partire dal valore principale come primo valore per l'array. I valori vengono continuamente posizionati leggendo l'albero da sinistra a destra, dall'alto verso il basso. Se un elemento è assente, la sua posizione nell'array viene saltata. Ogni nodo ha due figli. Se un nodo è a indice (posizione) n, il suo primo figlio nell'array è all'indice 2n+1 e il suo bambino successivo è all'indice 2n+2. 89 è all'indice 0; Il suo primo figlio, 85 è all'indice 2 (0)+1 = 1 mentre il suo secondo figlio è all'indice 2 (0)+2 = 2. 85 è all'indice 1; Il suo primo figlio, 84, è all'indice 2 (1)+1 = 3 mentre il suo secondo figlio, 82 è all'indice 2 (1)+2 = 4. 79 è all'indice 5; Il suo primo figlio, 65 è all'indice 2 (5)+1 = 11 mentre il suo secondo figlio è all'indice 2 (5)+2 = 12. Le formule vengono applicate al resto degli elementi nell'array.

Tale array, in cui il significato di un elemento e la relazione tra gli elementi, è implicito dalla posizione dell'elemento, è chiamato una struttura di dati implicita.

La struttura dei dati implicita per il minimo sopra è:

65, 68, 70, 73, 71, 83, 84 ,,, 79, 80 ,,, 85, 89

Il massimo sopra è un albero binario completo ma non un albero binario completo. Ecco perché alcune posizioni (posizioni) sono vuote nell'array. Per un albero binario completo, nessuna posizione sarà vuota nell'array.

Ora, se il mucchio fosse un albero quasi completo, ad esempio, se mancava il valore 82, allora l'array sarebbe:

89, 85, 87, 84 ,, 79, 73, 80, 81 ,,, 65, 69

In questa situazione, tre posizioni sono vuote. Tuttavia, le formule sono ancora applicabili.

Operazioni

Una struttura di dati è un formato di dati (e.G. un albero), oltre alla relazione tra i valori, più le operazioni (funzioni) funzionano sui valori. Per un mucchio, la relazione che attraversa l'intero mucchio è che il genitore deve essere uguale o maggiore di valore rispetto ai bambini, per un heap massimo; e il genitore deve essere uguale o meno valore rispetto ai bambini, per un minimo. Questa relazione è chiamata proprietà heap. Le operazioni di un mucchio sono raggruppate sotto i titoli della creazione, di base, interna e di ispezione. Segue un riassunto delle operazioni del heap:

Riepilogo delle operazioni di heap

Esistono alcune operazioni software che sono comuni con i cumuli, come segue:

Creazione di un mucchio

create_heap: creare un heap significa formare un oggetto che rappresenta il mucchio. Nel linguaggio C, è possibile creare un heap con il tipo di oggetto struct. Uno dei membri della struttura sarà l'array di heap. Il resto dei membri sarà funzioni (operazioni) per il mucchio. Create_heap significa creare un mucchio vuoto.

Heapify: l'array heap è un array parzialmente ordinato (ordinato). MEVIFICI DI HAPIFICA, fornire un array di heap da un array non desiderato - vedere i dettagli di seguito.

Unisci: questo significa, forma un cumulo di unione da due diversi cumuli: vedere i dettagli di seguito. I due cumuli dovrebbero essere entrambi heap massimo o entrambi i ministri. Il nuovo heap è conforme alla proprietà del heap, mentre i cumuli originali sono conservati (non cancellati).

Meld: questo significa. Il nuovo heap è in conformità con la proprietà del heap, mentre i cumuli originali vengono distrutti (cancellati). La differenza principale tra fusione e fusione è, che per la fusione, un albero si adatta a una sottostruttura alla radice dell'altro albero, consentendo valori duplicati nel nuovo albero, mentre per la fusione si forma un nuovo albero del mucchio, rimuovendo i duplicati. Non è necessario mantenere i due cumuli originali con la fusione.

Operazioni di heap di base

find_max (find_min): individuare il valore massimo nell'array massimo-heap e restituire una copia o individuare il valore minimo nell'array min-heap e restituire una copia.

Inserisci: aggiungi un nuovo elemento all'array heap e riorganizza l'array in modo che la proprietà heap del diagramma venga mantenuta.

estratto_max (estratto_min): individuare il valore massimo nell'array massimo-heap, rimuoverlo e restituirlo; o individuare il valore minimo nell'array min-heap, rimuoverlo e restituirlo.

delete_max (delete_min): individuare il nodo radice di un heap massimo, che è il primo elemento dell'array massimo-heap, rimuoverlo senza necessariamente restituirlo; o individuare il nodo radicale di un minimo, che è il primo elemento dell'array min-heap, rimuoverlo senza necessariamente restituirlo;

Sostituire: individuare il nodo radice di entrambi i heap, rimuoverlo e sostituirlo con uno nuovo. Non importa se la vecchia radice viene restituita.

Operazioni di heap interno

Aumin.

Elimina: elimina qualsiasi nodo, quindi riorganizza, in modo che la proprietà heap venga mantenuta per il heap massimo o un minimo.

Shift_up: sposta un nodo in un max heap o min-heap per tutto il tempo necessario, riorganizzando per mantenere la proprietà heap.

Shift_Down: sposta un nodo verso il basso in un heap massimo o un minuto per il tempo necessario, riorganizzando per mantenere la proprietà heap.

Ispezione di un mucchio

Misurare: Questo restituisce il numero di chiavi (valori) in un mucchio; Non include le posizioni vuote dell'array di heap. Un heap può essere rappresentato dal codice, come nel diagramma o con un array.

è vuoto: Questo restituisce vero booleano se non c'è nodo in un heap o falso booleano se il mucchio ha almeno un nodo.

Setacciare in un mucchio

C'è setacciatura e setaccia:

Setacciatura: Questo significa scambiare un nodo con il suo genitore. Se la proprietà heap non è soddisfatta, scambia il genitore con il proprio genitore. Continua in questo modo sul percorso fino a quando la proprietà heap non è soddisfatta. La procedura potrebbe raggiungere la radice.

Setacciatura: Ciò significa scambiare un nodo di grande valore con il più piccolo dei suoi due figli (o un bambino per un mucchio quasi completo). Se la proprietà heap non è soddisfatta, scambia il nodo inferiore con il nodo più piccolo dei suoi due figli. Continua in questo modo sul percorso fino a quando la proprietà heap non è soddisfatta. La procedura potrebbe raggiungere una foglia.

Accumulare

HeaPify significa ordinare un array non desiderato per avere la proprietà heap soddisfatta per max heap o min-heap. Ciò significa che potrebbero esserci alcune posizioni vuote nel nuovo array. L'algoritmo di base per accumulare un heap massimo o min-heap è il seguente:

- Se il nodo radice è più estremo di uno dei nodi del suo figlio, quindi scambia la radice con il nodo figlio meno estremo.

- Ripeti questo passaggio con i nodi per bambini in uno schema di attraversamento dell'albero pre-ordine.

L'albero finale è un albero di heap che soddisfa la proprietà. Un mucchio può essere rappresentato come un diagramma dell'albero o in un array. Il mucchio risultante è un albero parzialmente ordinato, io.e. Un array parzialmente ordinato.

Dettagli dell'operazione heap

Questa sezione dell'articolo fornisce i dettagli delle operazioni di heap.

Creazione di dettagli di heap

create_heap

Vedi sopra!

accumulare

Vedi sopra

unire

Se gli array di heap,

89, 85, 87, 84, 82, 79, 73, 80, 81 ,,, 65, 69

E

89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71

sono uniti, il risultato senza duplicati può essere,

89, 85, 87, 84, 82, 83, 81, 80, 79 ,, 73, 68, 65, 69, 70, 71

Dopo un po 'di setacciatura. Si noti che nel primo array, 82 non ha figli. Nell'array risultante, è all'indice 4; e le sue posizioni all'indice 2 (4)+1 = 9 e 2 (4)+2 = 10 sono vacanti. Ciò significa che inoltre non ha figli nel nuovo diagramma degli alberi. I due cumuli originali non devono essere eliminati poiché le loro informazioni non sono proprio nel nuovo heap (nuovo array). L'algoritmo di base per unire i cumuli dello stesso tipo è seguente:

- Unisciti a un array in fondo all'altro array.

- Heapify sta eliminando i duplicati, assicurandosi che i nodi che non avevano figli nel cumulo originale, non abbiano ancora figli nel nuovo mucchio.

Meld

L'algoritmo per fondere due cumuli dello stesso tipo (due o due minimi) è il seguente:

- Confronta i due nodi radicali.

- Rendi la radice meno estrema e il resto del suo albero (sottostruttura), il secondo figlio della radice estrema.

- Setacciare il figlio randagio della radice di ora la sottostruttura estrema, verso il basso nella sottostruttura estrema.

Il heap risultante è ancora conforme alla proprietà del heap, mentre i cumuli originali vengono distrutti (cancellati). I cumuli originali possono essere distrutti perché tutte le informazioni che possedevano sono ancora nel nuovo mucchio.

Operazioni di heap di base

find_max (find_min)

Ciò significa individuare il valore massimo nell'array massimo e restituire una copia o individuare il valore minimo nell'array min-heap e restituire una copia. Un array di heap per definizione soddisfa già la proprietà heap. Quindi, restituisci una copia del primo elemento dell'array.

inserire

Ciò significa aggiungere un nuovo elemento all'array heap e riorganizzare l'array in modo che la proprietà heap del diagramma sia mantenuta (soddisfatta). L'algoritmo per farlo per entrambi i tipi di cumuli è il seguente:

- Assumi un albero binario completo. Ciò significa che l'array deve essere riempito alla fine con posizioni vuote, se necessario. Il numero totale di nodi di un heap completo è 1 o 3 o 7 o 15 o 31, ecc.; Continua a raddoppiare e aggiungendo 1.

- Metti il ​​nodo nella posizione vuota più adatta per grandezza, verso l'estremità del mucchio (verso l'estremità dell'array di heap). Se non c'è una posizione vuota, inizia una nuova riga dal basso a sinistra.

- Setacciare se necessario, fino a quando la proprietà heap non è soddisfatta.

extract_max (extract_min)

Individua il valore massimo nell'array massimo, rimuoverlo e restituirlo; o individuare il valore minimo nell'array min-heap, rimuoverlo e restituirlo. L'algoritmo a Extract_max (extract_min) è il seguente:

- Rimuovi il nodo radice.

- Prendi (rimuovi) il nodo più in basso a destra (ultimo nodo nell'array) e posiziona sulla radice.

- Setacciare il punto appropriato, fino a quando la proprietà heap non è soddisfatta.

delete_max (delete_min)

Individua il nodo radice di un heap massimo, che è il primo elemento dell'array massimo-heap, rimuoverlo senza necessariamente restituirlo; o individuare il nodo radicale di un minimo, che è il primo elemento dell'array min-heap, rimuoverlo senza necessariamente restituirlo. L'algoritmo per eliminare il nodo radice è il seguente:

- Rimuovi il nodo radice.

- Prendi (rimuovi) il nodo più in basso a destra (ultimo nodo nell'array) e posiziona sulla radice.

- Setacciare il punto appropriato, fino a quando la proprietà heap non è soddisfatta.

sostituire

Individua il nodo radice di entrambi i heap, rimuoverlo e sostituirlo con quello nuovo. Non importa se la vecchia radice viene restituita. Setacciare se appropriato, fino a quando la proprietà heap non è soddisfatta.

Operazioni di heap interno

aumento_key (diminuzioni_key)

Aumenta il valore di qualsiasi nodo per un heap massimo e un riorganizzazione in modo che la proprietà heap venga mantenuta o diminuisci il valore di qualsiasi nodo per un minuto e un retrorange in modo che la proprietà heap sia mantenuta. Setacciare o giù come appropriato, fino a quando la proprietà heap non è soddisfatta.

eliminare

Rimuovere il nodo di interesse, quindi riorganizzare, in modo che la proprietà heap sia mantenuta per il massimo o un minimo. L'algoritmo per eliminare un nodo è il seguente:

- Rimuovi il nodo di interesse.

- Prendi (rimuovi) il nodo più in basso a destra (ultimo nodo nell'array) e posiziona l'indice del nodo rimosso. Se il nodo eliminato è all'ultima riga, questo potrebbe non essere necessario.

- Setacciare o giù come appropriato, fino a quando la proprietà heap non è soddisfatta.

Shift_up

Spostare un nodo in un max heap o un minuto per tutto il tempo necessario, riorganizzando per mantenere la proprietà del mucchio-setaccia.

Shift_Down

Spostare un nodo verso il basso in un heap massimo o un minuto per tutto il tempo necessario, riorganizzando per mantenere la proprietà del mucchio: setacciare.

Ispezione di un mucchio

misurare

Vedi sopra!

è vuoto

Vedi sopra!

Altre classi di cumuli

L'heap descritto in questo articolo può essere considerato come il mucchio principale (generale). Ci sono altre classi di cumuli. Tuttavia, i due che dovresti sapere oltre questo sono il mucchio binario e il mucchio D-ary.

Mucchio binario

Il mucchio binario è simile a questo mucchio principale, ma con più vincoli. In particolare, il mucchio binario deve essere un albero completo. Non confondere tra un albero completo e un albero completo.

d-ary heap

Un mucchio binario è un mucchio di 2. Un mucchio in cui ogni nodo ha 3 bambini è un mucchio di 3. Un mucchio in cui ogni nodo ha 4 bambini è un mucchio di 4 arti e così via. Un heap D-ary ha altri vincoli.

Conclusione

Un heap è un albero binario completo o quasi completo, che soddisfa la proprietà del heap. La proprietà HEAP ha 2 alternative: per un heap massimo, un genitore deve avere un valore uguale o maggiore rispetto ai bambini immediati; Per un minimo, un genitore deve essere uguale o inferiore rispetto ai bambini immediati. Un mucchio può essere rappresentato come un albero o in un array. Se rappresentato in un array, il nodo radice è il primo nodo dell'array; e se un nodo è all'indice n, il suo primo figlio nell'array è all'indice 2n+1 e il suo bambino successivo è all'indice 2n+2. Un heap ha alcune operazioni che vengono eseguite sull'array.

Chrys