Algoritmo di ordinamento heap (con codice in Python e C++)

Cos'è l'algoritmo di ordinamento heap?

Heap Sort è uno degli algoritmi di ordinamento più popolari e più veloci. È costruito sulla struttura dati completa dell'albero binario. Cercheremo l'elemento massimo e lo metteremo in primo piano per l'heap massimo. Lo metteremo sul nodo genitore dell'albero binario.

Diciamo che viene fornito un array, dati = [10,5, 7, 9, 4, 11, 45, 17, 60].

Nell'array, se l'indice i-esimo (i=0,1,2,3 …) è un nodo genitore, allora (2i+1) e (2i+2) saranno i figli sinistro e destro. La creazione di un albero binario completo con questo array sarà simile a questa:

Eseguiremo il processo heapify dall'inizio alla fine dell'array. Inizialmente, se convertiamo l'array in un albero, apparirà come sopra. Possiamo vedere che non mantiene alcuna proprietà heap (min-heap o max heap). Otterremo l'array ordinato eseguendo il processo heapify per tutti i nodi.

Applicazione dell'ordinamento heap

Ecco alcuni utilizzi dell'algoritmo di ordinamento dell'heap:

La costruzione di "code prioritarie" richiede l'ordinamento dell'heap. Perché heapsort mantiene l'elemento ordinato dopo ogni inserimento.
La struttura dei dati heap è efficiente nel trovare k^th elemento più grande in un dato array.
Il kernel Linux utilizza l'ordinamento heap come impostazione predefinita algoritmo di ordinamento poiché ha complessità spaziale O(1).

Crea ordinamento heap con l'esempio

Qui costruiremo un heap massimo dal seguente albero binario completo.

I nodi foglia sono 17, 60, 4, 11 e 45. Non hanno alcun nodo figlio. Ecco perché sono nodi foglia. Quindi, avvieremo il metodo heapify dal loro nodo padre. Ecco i passaggi:

Passo 1) Seleziona il sottoalbero più a sinistra. Se i nodi figli sono maggiori, scambia il nodo genitore con il nodo figlio.

Qui il nodo genitore è 9. E i nodi figli sono 17 e 60. Poiché 60 è il più grande, 60 e 9 verranno scambiati per mantenere il heap max.

Passo 2) Ora, il sottoalbero più a sinistra è heapificato. Il nodo genitore successivo è 7. Questo nodo genitore ha due nodi figli e il più grande è 45. Quindi, 45 e 7 verranno scambiati.

Passo 3) I nodi 60 e 4 hanno il nodo genitore 5. Poiché “5” è più piccolo del nodo figlio 60, verrà scambiato.

Passo 4) Ora, il nodo 5 ha il nodo figlio 17,9. Ciò non mantiene la proprietà heap massima. Quindi, 5 verrà sostituito con 17.

Passo 5) Il nodo 10 verrà scambiato con 60, quindi con 17. Il processo sarà simile al seguente.

Passo 6) Fino al passaggio 5 abbiamo creato l'heap massimo. Ogni nodo genitore è più grande dei suoi nodi figli. Il nodo radice ha il valore massimo (60).

Nota: Per creare l'array ordinato, dobbiamo sostituire il nodo con valore massimo con il suo successore.

Questo processo si chiama "estrarre massimo”. Poiché 60 è il nodo massimo, fisseremo la sua posizione sull'indice 0 e creeremo l'heap senza il nodo 60.

Passo 7) Quando viene rimosso 60, il valore massimo successivo è 45. Eseguiremo nuovamente il processo "Estrai Max" dal nodo 45.

Questa volta otterremo 45 e sostituiremo il nodo radice con il suo successore 17.

Dobbiamo esibirci”Estrai massimo" finché tutti gli elementi non saranno ordinati.

Dopo aver eseguito questi passaggi fino ad estrarre tutti i valori massimi, otterremo il seguente array.

Cos'è l'heap binario?

Un heap binario è una sorta di completo albero binario struttura dati. In questo tipo di struttura ad albero, il nodo genitore è maggiore o minore dei nodi figli. Se il nodo genitore è più piccolo, l'heap è chiamato "Min Heap" e se il nodo genitore è più grande, l'heap è chiamato "Max Heap".

Ecco alcuni esempi di heap minimo e heap massimo.

Nella figura sopra, se noti il "Min Heap", il nodo genitore è sempre più piccolo dei suoi nodi figli. In cima all'albero troviamo il valore più piccolo, 10.

Allo stesso modo, per il "Max Heap", il nodo genitore è sempre più grande dei nodi figli. L'elemento massimo è presente nel nodo head per il "Max Heap".

Che cosa è “Heapify”?

"Heapify" è il principio dell'heap che assicura la posizione del nodo. In Heapify, un heap massimo mantiene sempre una relazione con il padre e il figlio, e cioè il nodo padre sarà più grande dei nodi figlio.

Ad esempio, se viene aggiunto un nuovo nodo, dobbiamo rimodellare l'heap. Tuttavia, potremmo dover cambiare o scambiare i nodi o riorganizzare l'array. Questo processo di rimodellazione di un heap è chiamato "heapify".

Ecco un esempio di come funziona heapify:

Aggiunta di un nuovo nodo e Heapify — Aggiungere un nuovo nodo e heapify

Ecco i passaggi per heapify:

Passo 1) Aggiunto il nodo 65 come figlio destro del nodo 60.

Passo 2) Controlla se il nodo appena aggiunto è maggiore del genitore.

Passo 3) Poiché è più grande del nodo genitore, abbiamo scambiato il figlio destro con il suo genitore.

Come costruire l'heap

Prima di costruire l'heap o di heapificare un albero, dobbiamo sapere come lo memorizzeremo. Poiché l'heap è un albero binario completo, è meglio usare un schieramento per contenere i dati dell'heap.

Diciamo che un array contiene un totale di n elementi. Se l'indice "i" è un nodo genitore, il nodo sinistro sarà all'indice (2i+1)e il nodo destro sarà in indice (2i+2). Supponiamo che l'indice dell'array inizi da 0.

Utilizzando questo, memorizziamo un heap massimo in un array simile al seguente:

Rappresentazione basata su array dell'heap massimo

L'algoritmo heapify mantiene la proprietà heap. Se il genitore non ha il valore estremo (più piccolo o più grande), verrà scambiato con il nodo figlio più estremo.

Ecco i passaggi per heapizzare un heap massimo:

Passo 1) Inizia dal nodo foglia.

Passo 2) Trova il massimo tra genitore e figli.

Passo 3) Scambia i nodi se il nodo figlio ha un valore maggiore del genitore.

Passo 4) Sali di un livello.

Passo 5) Segui i passaggi 2,3,4 fino a raggiungere l'indice 0 o ordinare l'intero albero.

Ecco lo pseudo-codice per heapify ricorsivo (heap massimo):

def heapify():
  input→ array, size, i
  largest = i
  left = 2*i + 1
  right = 2*i + 2
if left<n and array[largest ] < array[left]:
  largest = left
if right<n and array[largest ] < array[right]:
  largest = right
If largest not equals i:
  swap(array[i],array[largest])
  heapify(array,n,largest)

Pseudo codice per l'ordinamento dell'heap

Ecco lo pseudo-codice per l'algoritmo di ordinamento dell'heap:

Heapify(numbers as an array, n as integer, i as integer):
  largest = i
  left = 2i+1
  right= 2i+2
if(left<=n) and (numbers[i]<numbers[left])
  largest=left
if(right<=n) and (numbers[i]<numbers[right])
  largest=right
if(largest  != i)
  swap(numbers[i], numbers[largest])
  Heapify(numbers,n,largest)
HeapSort(numbers as an array):
  n= numbers.size()
for i in range n/2 to 1
  Heapify(numbers,n,i)
for i in range n to 2
  Swap numbers[i] with numbers[1]
  Heapify(numbers,i,0)

Esempio di codice di ordinamento heap in C++

#include <iostream>
using namespace std;
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
void heapify(int numbers[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && numbers[left] < numbers[largest])
    {
        largest = left;
    }
    if (right < n && numbers[right] < numbers[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
	//uncomment the following line to see details in output
        //cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
        swap(numbers[i], numbers[largest]);
        heapify(numbers, n, largest);
    }
}
void heapSort(int numbers[], int n)
{
    for (int i = n/2 - 1; i >= 0; i--)
    {
        heapify(numbers, n, i);
//uncomment the following line to see details in output
 //cout<<"Heapify:\t";
  //display(numbers,n);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        swap(numbers[0], numbers[i]);
        heapify(numbers, i, 0);
    }
}
int main()
{
    int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    cout<<"Initial Array:\t";
    display(numbers,size);
    heapSort(numbers, size);
    cout<<"Sorted Array (descending order):\t";
    display(numbers, size);
}

Produzione:

Initial Array:  10      5       7       9       4       11      45      17      60
Sorted Array (descending order):  60      45      17      11      10      9       7       5       4

Esempio di codice di ordinamento heap in Python

def display(arr):
    for i in range(len(arr)):
    print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
    largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
    largest = left
if right < n and numbers[right] < numbers[largest]:
    largest = right
if largest != i:
    numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
    for i in range(n //2,-1,-1):
        heapify(items, n, i) for i in range(n - 1, -1, -1):
        items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)

Produzione:

Initial List:   10      5       7       9       4       11      45      17      60
After HeapSort: 60      45      17      11      10      9       7       5       4

Analisi della complessità temporale e spaziale di Heap Sort

Ci sono complessità temporale e complessità spaziale che possiamo analizzare per l'ordinamento heap. Per la complessità temporale abbiamo i seguenti casi:

Caso migliore
Caso medio
Caso peggiore

L'heap è implementato su un albero binario completo. Quindi, al livello più basso dell'albero binario, ci sarà il numero massimo di nodi. Se il livello inferiore ha n nodi, il livello superiore avrà n/2 nodi.

In questo esempio, il livello 3 ha quattro elementi, il livello 2 ha due elementi e il livello 1 ha un elemento. Se è presente un numero totale di n elementi, l'altezza o il livello totale sarà Log₂(N). Pertanto, l'inserimento di un singolo elemento potrebbe richiedere un massimo di iterazioni Log(n).

Quando vogliamo prendere il valore massimo dall'heap, prendiamo semplicemente il nodo radice. Poi, eseguiamo di nuovo heapify. Ogni heapify prende Log₂(N) tempo. L'estrazione del massimo richiede tempo O(1).

migliori Complessità temporale del caso per l'algoritmo di ordinamento heap

Quando tutti gli elementi sono già ordinati nell'array, ci vorrà O(n) tempo per costruire l'heap. Perché se l'elenco è ordinato, l'inserimento di un elemento richiederà il tempo costante O(1).

Quindi, nel migliore dei casi, ci vorrà O (n) tempo per creare un heap massimo o minimo.

Complessità temporale media del caso per l'algoritmo di ordinamento heap

L'inserimento di un elemento o l'estrazione di un costo massimo richiede tempo O(log(n)), quindi la complessità temporale media per l'algoritmo di ordinamento heap è O(nlog(n)).

Complessità temporale del caso peggiore per l'algoritmo di ordinamento heap

Similmente al caso medio, nello scenario peggiore, potremmo eseguire heapify n volte. Ogni heapify costerà O(log(n)) di tempo. Quindi, la complessità temporale del caso peggiore sarà O(nlog(n)).

Complessità spaziale per l'algoritmo di ordinamento heap

Heap sort è un algoritmo progettato in loco. Ciò significa che non è necessaria memoria extra o temporanea per eseguire l'attività. Se osserviamo l'implementazione, noteremo che abbiamo utilizzato swap() per eseguire lo scambio dei nodi. Non è stato necessario nessun altro elenco o array. Quindi, la complessità dello spazio è O(1).