Phenquestions
Illustrazione delle strutture di dati dell'heap
Esistono due tipi di heap: max-heap e min-heap. Una struttura max-heap è dove il valore massimo è la radice ei valori diventano più piccoli man mano che l'albero scende; ogni genitore ha un valore uguale o maggiore di uno dei suoi figli immediati. Una struttura min-heap è dove il valore minimo è la radice ei valori diventano più grandi man mano che l'albero scende; ogni genitore ha un valore uguale o inferiore a uno dei suoi figli immediati. Nei seguenti diagrammi, il primo è un max-heap e il secondo è un min-heap:
Per entrambi i cumuli, nota che per una coppia di bambini, non importa se quello a sinistra è il valore più grande. Una riga in un livello nell'albero, non deve essere necessariamente riempita dal minimo al massimo, da sinistra; non è anche necessariamente riempito dal massimo al minimo, da sinistra.
Rappresentazione di un heap in un array
Affinché il software possa utilizzare facilmente un heap, l'heap deve essere rappresentato in un array. Il max-heap sopra, rappresentato in un array è:
89, 85, 87, 84, 82, 79, 73, 80, 81, , , 65, 69Questo viene fatto iniziando con il valore radice come primo valore per l'array. I valori vengono posizionati continuamente 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 è all'indice (posizione) n, il suo primo figlio nell'array è all'indice 2n+1 e il suo figlio successivo è all'indice 2n+2. 89 è all'indice 0; il suo primo figlio, 85 è all'indice 2(0)+1=1 mentre il 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 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 nella posizione dell'elemento, è chiamato una struttura dati implicita.
La struttura dati implicita per il min-heap sopra è:
65, 68, 70, 73, 71, 83, 84, , , 79, 80, , , 85, 89Il max-heap 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 l'heap fosse un albero quasi completo, ad esempio, se mancasse il valore 82, l'array sarebbe:
89, 85, 87, 84, , 79, 73, 80, 81, , , 65, 69In questa situazione, tre posizioni sono vuote. Tuttavia, le formule sono ancora applicabili.
Operazioni
Una struttura dati è un formato di dati (e.g. un albero), più la relazione tra i valori, più le operazioni (funzioni) eseguite sui valori. Per un heap, la relazione che attraversa l'intero heap è che il genitore deve avere un valore uguale o maggiore dei figli, per un max-heap; e il genitore deve essere uguale o inferiore in valore ai figli, per un min-heap. Questa relazione è chiamata proprietà dell'heap. Le operazioni di un mucchio sono raggruppate sotto le intestazioni di Creazione, Base, Interno e Ispezione. Segue un riepilogo delle operazioni dell'heap:
Riepilogo operazioni heap
Esistono alcune operazioni software comuni con gli heap, come segue:
Creazione di un mucchio
create_heap: creare un heap significa formare un oggetto che rappresenta l'heap. Nel linguaggio C, puoi creare un heap con il tipo di oggetto struct. Uno dei membri della struttura sarà l'array heap. Il resto dei membri saranno funzioni (operazioni) per l'heap. Create_heap significa creare un heap vuoto.
Heapify: l'array heap è un array parzialmente ordinato (ordinato). Heapify significa fornire un array di heap da un array non ordinato - vedere i dettagli di seguito.
Unisci: Ciò significa formare un heap di unione da due heap diversi - vedere i dettagli di seguito. I due heap dovrebbero essere entrambi max-heap o entrambi min-heap. Il nuovo heap è conforme alla proprietà heap, mentre gli heap originali vengono conservati (non cancellati).
Combina: Questo significa unire due heap dello stesso tipo per formarne uno nuovo, mantenendo i duplicati - vedere i dettagli di seguito. Il nuovo heap è conforme alla proprietà heap, mentre gli heap originali vengono distrutti (cancellati). La principale differenza tra fusione e fusione è che per la fusione, un albero si adatta come sottoalbero alla radice dell'altro albero, consentendo valori duplicati nel nuovo albero, mentre per la fusione, viene formato un nuovo albero heap, rimuovendo i duplicati. Non è necessario mantenere i due cumuli originali con la fusione.
Operazioni di base sull'heap
find_max (find_min): individua il valore massimo nell'array max-heap e restituisce una copia, oppure individua il valore minimo nell'array min-heap e restituisce una copia.
Inserisci: aggiunge un nuovo elemento all'array heap e riorganizza l'array in modo che venga mantenuta la proprietà heap del diagramma.
extract_max (extract_min): individuare il valore massimo nell'array max-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 max-heap, che è il primo elemento dell'array max-heap, rimuoverlo senza necessariamente restituirlo; oppure individuare il nodo radice di un min-heap, che è il primo elemento dell'array min-heap, rimuoverlo senza necessariamente restituirlo;
Sostituisci: individua il nodo radice di entrambi gli heap, rimuovilo e sostituiscilo con uno nuovo. Non importa se viene restituita la vecchia radice.
Operazioni heap interne Internal
aumentare_chiave (decrease_key): Aumentare il valore di qualsiasi nodo per un max-heap e riorganizzare in modo che la proprietà dell'heap venga mantenuta, o diminuire il valore di qualsiasi nodo per un minimo-heap e riorganizzare in modo che la proprietà dell'heap venga mantenuta.
Elimina: elimina qualsiasi nodo, quindi riorganizza, in modo che la proprietà dell'heap venga mantenuta per il max-heap o un min-heap.
shift_up: sposta un nodo in alto in un max-heap o min-heap per tutto il tempo necessario, riorganizzandolo per mantenere la proprietà dell'heap.
shift_down: sposta un nodo verso il basso in un max-heap o min-heap per tutto il tempo necessario, riorganizzandolo per mantenere la proprietà dell'heap.
Ispezione di un mucchio
Dimensione: Restituisce il numero di chiavi (valori) in un heap; non include le posizioni vuote dell'array heap. Un heap può essere rappresentato da codice, come nel diagramma, o con un array.
è vuoto: Restituisce Boolean true se non ci sono nodi in un heap o boolean false se l'heap ha almeno un nodo.
Setacciare in un mucchio
C'è setacciare e setacciare:
Setacciare: Questo significa scambiare un nodo con il suo genitore. Se la proprietà dell'heap non è soddisfatta, scambia il genitore con il suo genitore. Continua in questo modo nel percorso finché la proprietà dell'heap non è soddisfatta. La procedura potrebbe raggiungere la radice.
Setacciare: Ciò significa scambiare un nodo di grande valore con il più piccolo dei suoi due figli (o un figlio per un heap quasi completo). Se la proprietà dell'heap non è soddisfatta, scambia il nodo inferiore con il nodo più piccolo dei suoi due figli. Continua in questo modo nel percorso finché la proprietà dell'heap non è soddisfatta. La procedura potrebbe raggiungere una foglia.
accumulando
Heapify significa ordinare un array non ordinato 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 heapify un max-heap o min-heap è il seguente:
- se il nodo radice è più estremo di uno dei suoi nodi figlio, allora scambia la radice con il nodo figlio meno estremo.
- Ripeti questo passaggio con i nodi figli in uno schema di attraversamento albero preordinato.
L'albero finale è un albero heap che soddisfa la proprietà heap. Un heap può essere rappresentato come un diagramma ad albero o in un array. L'heap risultante è un albero parzialmente ordinato, i.e. un array parzialmente ordinato.
Dettagli operazione heap
Questa sezione dell'articolo fornisce i dettagli delle operazioni sull'heap.
Creazione di un Heap Dettagli
create_heap
Vedi sopra!
ammassare
Vedi sopra
unire
Se gli array di heap,
89, 85, 87, 84, 82, 79, 73, 80, 81, , , 65, 69e
89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71vengono uniti, il risultato senza duplicati potrebbe essere,
89, 85, 87, 84, 82, 83, 81, 80, 79, , 73, 68, 65, 69, 70, 71Dopo aver setacciato. Nota 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 anche che non ha figli nel nuovo diagramma ad albero. I due heap originali non dovrebbero essere eliminati poiché le loro informazioni non sono realmente nel nuovo heap (nuovo array). L'algoritmo di base per unire gli heap dello stesso tipo è il seguente:
- Unisci un array alla fine dell'altro array.
- Heapify sta eliminando i duplicati, assicurandosi che i nodi che non avevano figli negli heap originali, non abbiano ancora figli nel nuovo heap.
fondere
L'algoritmo per unire due heap dello stesso tipo (due max o due min) è il seguente:
- Confronta i due nodi radice.
- Crea la radice meno estrema e il resto del suo albero (sottoalbero), il secondo figlio della radice estrema.
- Setacciare il figlio randagio della radice di adesso l'estremo sottoalbero, in basso nell'estremo sottoalbero.
L'heap risultante è ancora conforme alla proprietà dell'heap, mentre gli heap originali vengono distrutti (cancellati). Gli heap originali possono essere distrutti perché tutte le informazioni in loro possesso sono ancora nel nuovo heap.
Operazioni di base sull'heap
trova_max (find_min)
Ciò significa individuare il valore massimo nell'array max-heap e restituire una copia, oppure individuare il valore minimo nell'array min-heap e restituire una copia. Un array heap per definizione soddisfa già la proprietà heap. Quindi, restituisci semplicemente 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 venga mantenuta (soddisfatta). L'algoritmo per eseguire questa operazione per entrambi i tipi di heap è 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 ad aggiungere 1.
- Metti il nodo nella posizione vuota più adatta per grandezza, verso la fine dell'heap (verso la fine dell'array dell'heap). Se non ci sono posizioni vuote, inizia una nuova riga in basso a sinistra.
- Setacciare se necessario, fino a quando la proprietà dell'heap è soddisfatta.
estrazione_max (estrazione_min)
Individua il valore massimo nell'array max-heap, rimuovilo e restituiscilo; o individuare il valore minimo nell'array min-heap, rimuoverlo e restituirlo. L'algoritmo per estrarre_max (extract_min) è il seguente:
- Rimuovi il nodo radice.
- Prendi (rimuovi) il nodo in basso a destra (ultimo nodo nell'array) e posizionalo alla radice.
- Setacciare come appropriato, fino a quando la proprietà dell'heap è soddisfatta.
delete_max (delete_min)
Individua il nodo radice di un max-heap, che è il primo elemento dell'array max-heap, rimuovilo senza necessariamente restituirlo; o individuare il nodo radice di un min-heap, 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 in basso a destra (ultimo nodo nell'array) e posizionalo alla radice.
- Setacciare come appropriato, fino a quando la proprietà dell'heap è soddisfatta.
sostituire
Individua il nodo radice di entrambi gli heap, rimuovilo e sostituiscilo con quello nuovo. Non importa se viene restituita la vecchia radice. Setacciare se appropriato, fino a quando la proprietà dell'heap è soddisfatta.
Operazioni heap interne Internal
chiave_aumento (chiave_diminuzione)
Aumentare il valore di qualsiasi nodo per un max-heap e riorganizzare in modo da mantenere la proprietà dell'heap o diminuire il valore di qualsiasi nodo per un min-heap e riorganizzare in modo che la proprietà dell'heap venga mantenuta. Setacciare verso l'alto o verso il basso a seconda dei casi, fino a quando la proprietà dell'heap è soddisfatta.
Elimina
Rimuovere il nodo di interesse, quindi riorganizzare, in modo che la proprietà dell'heap venga mantenuta per il max-heap o un min-heap. L'algoritmo per eliminare un nodo è il seguente:
- Rimuovere il nodo di interesse.
- Prendi (rimuovi) il nodo in basso a destra (ultimo nodo nell'array) e posizionalo all'indice del nodo rimosso. Se il nodo eliminato si trova nell'ultima riga, potrebbe non essere necessario.
- Setacciare verso l'alto o verso il basso a seconda dei casi, fino a quando la proprietà dell'heap è soddisfatta.
shift_up
Sposta un nodo in alto in un heap massimo o minimo per tutto il tempo necessario, riorganizzando per mantenere la proprietà dell'heap - setacciare.
shift_down
Sposta un nodo verso il basso in un max-heap o min-heap per tutto il tempo necessario, riorganizzandolo per mantenere la proprietà dell'heap - setacciare verso il basso.
Ispezione di un mucchio
dimensione
Vedi sopra!
è vuoto
Vedi sopra!
Altre classi di cumuli
L'heap descritto in questo articolo può essere considerato come l'heap principale (generale). Ci sono altre classi di cumuli. Tuttavia, i due che dovresti conoscere oltre a questo sono il Binary Heap e il d-ary Heap.
Mucchio binario
L'heap binario è simile a questo heap principale, ma con più vincoli. In particolare, l'heap binario deve essere un albero completo. Non confondere tra un albero completo e un albero completo.
d-ary Heap
Un mucchio binario è un mucchio 2-arioary. Un mucchio in cui ogni nodo ha 3 figli è un mucchio 3-ario 3-. Un heap in cui ogni nodo ha 4 figli è un heap di 4 arie, e così via. Un heap d-ary ha altri vincoli.
Conclusione
Un heap è un albero binario completo o quasi completo, che soddisfa la proprietà heap. La proprietà heap ha 2 alternative: per un max-heap, un genitore deve avere un valore uguale o maggiore dei figli immediati; per un min-heap, un genitore deve avere un valore uguale o inferiore ai figli immediati. Un heap può essere rappresentato come un albero o in un array. Quando 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 figlio successivo è all'indice 2n+2. Un heap ha determinate operazioni che vengono eseguite sull'array.
cris
