Strutture dati heap
Heap è un caso speciale di struttura dati ad albero binario bilanciato in cui la chiave del nodo radice viene confrontata con i suoi figli e organizzata di conseguenza. Seα ha un nodo figlio β poi -
chiave (α) ≥ chiave (β)
Poiché il valore di parent è maggiore di quello di child, questa proprietà genera Max Heap. In base a questo criterio, un mucchio può essere di due tipi:
For Input → 35 33 42 10 14 19 27 44 26 31
Min-Heap - Dove il valore del nodo radice è minore o uguale a uno dei suoi figli.
Max-Heap - Dove il valore del nodo radice è maggiore o uguale a uno dei suoi figli.
Entrambi gli alberi vengono costruiti utilizzando lo stesso input e l'ordine di arrivo.
Algoritmo di costruzione Max Heap
Useremo lo stesso esempio per dimostrare come viene creato un Max Heap. La procedura per creare Min Heap è simile, ma usiamo valori minimi invece di valori massimi.
Deriveremo un algoritmo per max heap inserendo un elemento alla volta. In qualsiasi momento, l'heap deve mantenere la sua proprietà. Durante l'inserimento, assumiamo anche di inserire un nodo in un albero già accumulato.
Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.
Note - Nell'algoritmo di costruzione Min Heap, ci aspettiamo che il valore del nodo padre sia inferiore a quello del nodo figlio.
Comprendiamo la costruzione di Max Heap con un'illustrazione animata. Consideriamo lo stesso campione di input che abbiamo usato in precedenza.
Algoritmo di eliminazione dell'heap massimo
Deriviamo un algoritmo da eliminare da max heap. L'eliminazione nell'heap massimo (o minimo) avviene sempre alla radice per rimuovere il valore massimo (o minimo).
Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.