La seguente classe permette di creare un HeapTree e di effettuare una serie di azioni su di esso
È possibile effettuare operazioni di ordinamento dell'HeapTree decidendo pure se deve essere ordinato per valori decrescenti (maxHeapSort) o valori crescenti (minHeapSort)
È possibile aggiungere uno o più nodi alla fine dell'HeapTree (aggiunta di foglie)
L'intera struttura dati è contenuta all'interno di un array di oggetti Node
Ogni Node è un oggetto definito dalla libreria Cytoscape.js
In questi esempi vengono visualizzati i metodi maxHeapify e minHeapSort, quindi visualizzeremo in questo esempio un algoritmo in cui dopo il sorting l'HeapTree sarà ordinato in modo crescente
Come primo step dobbiamo piazzarci in quello che viene definito il Floor di un HeapTree. Si parte dalla posizione size/2 per poi sfruttare il metodo maxHeapify in maniera ricorsiva su tutti i nodi precedenti
A questo punto si procede allo swapping e heapify dei valori all'interno dell'HeapTree.
Lo swapping avviene tra il primo e l'ultimo elemento dell'HeapTree il cui indice corrisponde a size (variabile che in questo momento viene modificata per poi essere ripristinata)
Dopo aver effettuato lo swapping si procede con il maxHeapify del primo elemento all'interno dell'HeapTree
I precedenti due passaggi verranno eseguiti fino a quando non si arriverà al primo elemento dell'HeapTree
Di seguito verrà visualizzato il codice della funzione minHeapSort (il codice sarà riportato nuovamente all'interno della documentazione dei metodi pubblibi )
Viene riportata solo una parte della funzione essendo che, all'interno di essa, vengono eseguite funzioni di manipolazione del DOM
for(let i = Math.floor(size/2)-1;i>=0;i--){
maxHeapify(i);
}
let oldSize = size;
for(let i = heap.length-1;i>0;i--)
{
[heap[0], heap[i]]=[heap[i], heap[0]]
size--
maxHeapify(0);
}
size = oldSize
Main Class HeapTree
Variabili
r = Oggetto di tipo Random (contenente seed=50) che permette la generazione casuale di numeri (usato principalmente per test)
size = Variabile di tipo int che contiene la lunghezza dell'HeapTree
heap[] = Array di Node che rappresenta l'HeapTree
Metodi pubblici di HeapTree
HeapTree(int n )
Metodo costruttore che crea l'heap casualmente dato un numero di nodi
HeapTree(int[] arr )
Metodo costruttore che crea l'heap dato un array di valori interi
printHeap()
Metodo che stampa l'heap per livelli
maxHeapify(int i)
Metodo che, in caso il nodo figlio sia più grande del genitore, scambi i due nodi e successivamente procede in maniera ricorsiva con i nodi sucessivi fino a quando un genitore non sarà più grande dei figli
Node largest = heap[i];
if (i*2+1 < size && heap[i*2+1].val > heap[i].val){
largest = heap[i*2+1];
}
if (i*2+2 < size && heap[i*2+2].val > heap[i].val &&heap[i*2+2].val>largest.val ) {
largest = heap[i*2+2];
}
if (largest.pos != i) {
swap(heap[i], largest);
maxHeapify(largest.pos);
}
minHeapify(int i)
Metodo che, in caso il nodo figlio sia più piccolo del genitore, scambi i due nodi e successivamente procede in maniera ricorsiva con i nodi sucessivi fino a quando un genitore non sarà più piccolo dei figli
Node largest = heap[i];
if (i*2+1 < size && heap[i*2+1].val < heap[i].val){
largest = heap[i*2+1];
}
if (i*2+2 < size && heap[i*2+2].val < heap[i].val &&heap[i*2+2].val>largest.val ) {
largest = heap[i*2+2];
}
if (largest.pos != i) {
swap(heap[i], largest);
minHeapify(largest.pos);
}
maxHeapSort()
Metodo che, sfruttando minHeapify, riordina l'heap dal valore più grande al più piccolo
for(int i = size/2-1;i>=0;i--)
minHeapify(i);
int oldSize = size;
for (size-=1; size>=0; size--)
{
swap(heap[0], heap[size]);
minHeapify(0);
}
size = oldSize;//essendo che lavoro con un parametro dell'heap e voglio comunque mantenerlo nel tempo per altre operazioni, sfrutto questa variabile di supporto
minHeapSort()
Metodo che, sfruttando maxHeapify, riordina l'heap dal valore più piccolo al più grande
for(int i = size/2-1;i>=0;i--)
maxHeapify(i);
int oldSize = size;
for (size-=1; size>=0; size--)
{
swap(heap[0], heap[size]);
maxHeapify(0);
}
size = oldSize;//essendo che lavoro con un parametro dell'heap e voglio comunque mantenerlo nel tempo per altre operazioni, sfrutto questa variabile di supporto
addNode(int nodeVal)
Metodo che aggiunge un nodo alla fine dell'heap
addNode(int[] nodeVal)
Metodo che aggiunge una serie di nodi alla fine dell'heap
deleteNode()
Metodo che elimina l'ultimo nodo (nonché foglia) dell'heap
Metodi privati di HeapTree
swap(Node i, Node j)
Metodo che scambia il valore contenuto nei due nodi
Nested Class Node
Variabili
val = Variabile di tipo int che contiene il valore del nodo
pos = Variabile di tipo int che contiene la posizione all'interno dell'HeapTree
Metodi pubblici di Node
Node(int val, int pos)
Metodo costruttore che dato il valore e la posizione di un nodo all'interno di un heap, crea il nodo
Node(Node n)
Metodo costruttore che, dato un nodo, ne crea uno uguale
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent