DAA - Metodo di inserimento

Per inserire un elemento in un heap, il nuovo elemento viene inizialmente aggiunto alla fine dell'heap come ultimo elemento dell'array.

Dopo aver inserito questo elemento, la proprietà heap potrebbe essere violata, quindi la proprietà heap viene riparata confrontando l'elemento aggiunto con il suo genitore e spostando l'elemento aggiunto di un livello, scambiando le posizioni con il genitore. Questo processo è chiamatopercolation up.

Il confronto viene ripetuto fino a quando il genitore è maggiore o uguale all'elemento percolatore.

Algorithm: Max-Heap-Insert (numbers[], key) 
heapsize = heapsize + 1 
numbers[heapsize] = -∞ 
i = heapsize 
numbers[i] = key 
while i > 1 and numbers[Parent(numbers[], i)] < numbers[i] 
   exchange(numbers[i], numbers[Parent(numbers[], i)]) 
   i = Parent (numbers[], i)

Analisi

Inizialmente, un elemento viene aggiunto alla fine della matrice. Se viola la proprietà heap, l'elemento viene scambiato con il suo genitore. L'altezza dell'albero èlog n. Massimolog n numero di operazioni da eseguire.

Quindi, la complessità di questa funzione è O(log n).

Esempio

Consideriamo un max-heap, come mostrato di seguito, in cui è necessario aggiungere un nuovo elemento 5.

Inizialmente, 55 verranno aggiunti alla fine di questo array.

Dopo l'inserimento, viola la proprietà heap. Quindi, l'elemento deve essere scambiato con il suo genitore. Dopo lo scambio, l'heap avrà il seguente aspetto.

Ancora una volta, l'elemento viola la proprietà di heap. Quindi, viene scambiato con il suo genitore.

Adesso dobbiamo fermarci.