DAA - Metodo di estrazione

Il metodo Extract viene utilizzato per estrarre l'elemento radice di un heap. Di seguito è riportato l'algoritmo.

Algorithm: Heap-Extract-Max (numbers[]) 
max = numbers[1] 
numbers[1] = numbers[heapsize] 
heapsize = heapsize – 1 
Max-Heapify (numbers[], 1) 
return max

Esempio

Consideriamo lo stesso esempio discusso in precedenza. Ora vogliamo estrarre un elemento. Questo metodo restituirà l'elemento radice dell'heap.

Dopo la cancellazione dell'elemento radice, l'ultimo elemento verrà spostato nella posizione radice.

Ora verrà chiamata la funzione Heapify. Dopo Heapify, viene generato il seguente heap.