Esercizi svolti di informatica n.7

Dato un heap H di n elementi, descrivere a parole l’algoritmo che cancella un prefissato nodo e riaggiusta l’heap risultante di n-1 elementi.
Valutare la complessità dell’algoritmo presentato.

SOLUZIONE.

Il problema si scomplone in due parti: la prima consiste nel cercare l’elemento da eliminare, e l’altra nel cancellarlo e ripristinare l’heap.

L’elemento i da eliminare può essere inteso come l’elemento di posizione i oppure l’elemento di chiave i. Nel primo caso l’individuazione dell’elemento richiede tempo costante (l’elemento è H[i]), nel secondo bisogna effettuare una ricerca, che può richiedere anche tempo lineare in n, cioè O(n).

Una volta noto l’elemento, sia esso H[x], è possibile eliminarlo apparentemente in molti modi:

• si può portare verso le foglie l’elemento da cancellare scambiandolo con il maggiore dei suoi figli; una volta che l’elemento ha raggiunto le foglie, si elimina semplicemente; questo algoritmo e’ errato perche’ un heap è un albero binario completo o quasi completo e questo approccio può far perdere questa proprietà;

30 30

/ \ / \

20 12 9 12

/ \ / \ / / \

8 9 1 10 8 1 10

• si può shiftare tutti gli elementi H[x+1], H[x+2], …, H[n] di una posizione verso sinistra e poi riaggiustare l’heap, ma questa tecnica, seppure formalmente corretta risulta essere troppo costosa in termini di tempo, in fatti lo shift a sinistra provoca un disallineamento dei figli rispetto ai padri per cui nessun nodo è garantito mantenere la proprietà dell’heap, che – per essere aggiustato – deve essere interamente ricostruito;

30 12

/ \ / \

12 20 20 8

/ \ / \ / \ /

8 9 1 17 9 1 17

• si può scambiare H[x] con H[n], cioè con la foglia più a sinistra, eliminare tale foglia e riaggiustare l’heap risultante. Per fare ciò, bisogna confrontare il nuovo H[x] con il maggiore dei suoi figli; se H[x] risulta minore, si può applicare la funzione di aggiustamento dell’heap top-down; se H[x] sembra in posizione corretta rispetto ai suoi figli, non è ancora detto che l’heap sia corretto, bisogna infatti confrontarlo con il padre, se questo è minore di H[x] si deve procedere all’aggiustamento bottom-up.

30 30 30 30

/ \ / \ / \ / \

12 20 => 7 20 12 20 => 12 20

/ \ / \ / \ / / \ / \ / \ /

8 9 1 7 8 9 1 8 9 1 17 17 9 1

top-down bottom-up

Se escludiamo la ricerca del nodo, l’algoritmo di cancellazione e riaggiustamento ha una complessità pari al massimo tra la complessità dell’aggiustamento top-down e di quello bottom-up. Poiché entrambi si possono eseguire in tempo O(log n), ne consegure che O(log n) è proprio la complessità dell’algoritmo presentato.