logo

TechCodeview

Ordinamento heap: tutorial su strutture dati e algoritmi

Ordinamento dell'heap è una tecnica di ordinamento basata sul confronto basata su Heap binario struttura dati. È simile al ordinamento della selezione dove troviamo prima l'elemento minimo e posizioniamo l'elemento minimo all'inizio. Ripeti lo stesso procedimento per i restanti elementi.

Algoritmo di ordinamento dell'heap

Per risolvere il problema seguire l'idea seguente:



multiplexing

Per prima cosa converti l'array in una struttura dati heap utilizzando heapify, quindi elimina uno per uno il nodo radice dell'heap Max e sostituiscilo con l'ultimo nodo nell'heap, quindi crea heap la radice dell'heap. Ripetere questo processo finché la dimensione dell'heap non è maggiore di 1.

  • Crea un heap dall'array di input fornito.
  • Ripetere i seguenti passaggi finché l'heap non contiene un solo elemento:
    • Scambia l'elemento radice dell'heap (che è l'elemento più grande) con l'ultimo elemento dell'heap.
    • Rimuovi l'ultimo elemento dell'heap (che ora è nella posizione corretta).
    • Heapificare gli elementi rimanenti dell'heap.
  • L'array ordinato si ottiene invertendo l'ordine degli elementi nell'array di input.
Problema consigliato Risolvilo prima con la PRATICA, prima di passare alla soluzione Risolvi il problema

Funzionamento dettagliato dell'ordinamento dell'heap

Per comprendere più chiaramente l'ordinamento dell'heap, prendiamo un array non ordinato e proviamo a ordinarlo utilizzando l'ordinamento dell'heap.
Considera l'array: arr[] = {4, 10, 3, 5, 1}.

Costruisci un albero binario completo: Costruisci un albero binario completo dall'array.



Algoritmo di ordinamento dell'heap | Costruisci un albero binario completo

Trasforma in heap massimo: Successivamente, il compito è costruire un albero da quell'array non ordinato e provare a convertirlo mucchio massimo.

  • Per trasformare un heap in un max-heap, il nodo genitore dovrebbe sempre essere maggiore o uguale ai nodi figli
    • Qui, in questo esempio, come nodo genitore 4 è più piccolo del nodo figlio 10, quindi, scambiali per creare un heap massimo.
  • Ora, 4 poiché un genitore è più piccolo del bambino 5 , quindi scambiali nuovamente entrambi e l'heap e l'array risultanti dovrebbero essere così:

Algoritmo di ordinamento dell'heap | Max Heapify ha costruito un albero binario



Esegui l'ordinamento dell'heap: Rimuovi l'elemento massimo in ogni passaggio (ovvero spostalo nella posizione finale e rimuovilo) quindi considera gli elementi rimanenti e trasformalo in un heap massimo.

  • Elimina l'elemento radice (10) dall'heap massimo. Per eliminare questo nodo, prova a scambiarlo con l'ultimo nodo, ad es. (1). Dopo aver rimosso l'elemento root, esegui nuovamente l'heap per convertirlo nell'heap massimo.
    • L'heap e l'array risultanti dovrebbero assomigliare a questo:

Algoritmo di ordinamento dell'heap | Rimuovi il massimo da root e max heapify

  • Ripeti i passaggi precedenti e apparirà come segue:

Algoritmo di ordinamento dell'heap | Rimuovi il massimo successivo da root e max heapify

  • Ora rimuovi nuovamente la radice (cioè 3) ed esegui heapify.

Algoritmo di ordinamento dell'heap | Ripetere il passaggio precedente

data da stringere
  • Ora, quando la radice viene rimossa ancora una volta, viene ordinata. e l'array ordinato sarà come arr[] = {1, 3, 4, 5, 10} .

Algoritmo di ordinamento dell'heap | Array ordinato finale

comando di installazione npm

Implementazione dell'Heap Sort

C++ 
// C++ program for implementation of Heap Sort #include  using namespace std; // To heapify a subtree rooted with node i // which is an index in arr[]. // n is size of heap void heapify(int arr[], int N, int i) {  // Initialize largest as root  int largest = i;  // left = 2*i + 1  int l = 2 * i + 1;  // right = 2*i + 2  int r = 2 * i + 2;  // If left child is larger than root  if (l < N && arr[l]>arr[più grande]) più grande = l;  // Se il bambino destro è più grande del più grande // finora if (r< N && arr[r]>arr[più grande]) più grande = r;  // Se il più grande non è root if (largest != i) { swap(arr[i], arr[largest]);  // Heapify ricorsivamente il // sottoalbero interessato heapify(arr, N, large);  } } // Funzione principale per eseguire l'ordinamento dell'heap void heapSort(int arr[], int N) { // Costruisci l'heap (riorganizza l'array) per (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i);  // Uno per uno estrae un elemento // dall'heap for (int i = N - 1; i> 0; i--) { // Sposta la radice corrente alla fine swap(arr[0], arr[i]);  // chiama max heapify sull'heap ridotto heapify(arr, i, 0);  } } // Una funzione di utilità per stampare un array di dimensione n void printArray(int arr[], int N) { for (int i = 0; i< N; ++i)  cout << arr[i] << ' ';  cout << '
'; } // Driver's code int main() {  int arr[] = { 12, 11, 13, 5, 6, 7 };  int N = sizeof(arr) / sizeof(arr[0]);  // Function call  heapSort(arr, N);  cout << 'Sorted array is 
';  printArray(arr, N); }>
C 
// Heap Sort in C #include  // Function to swap the position of two elements void swap(int* a, int* b) {  int temp = *a;  *a = *b;  *b = temp; } // To heapify a subtree rooted with node i // which is an index in arr[]. // n is size of heap void heapify(int arr[], int N, int i) {  // Find largest among root,  // left child and right child  // Initialize largest as root  int largest = i;  // left = 2*i + 1  int left = 2 * i + 1;  // right = 2*i + 2  int right = 2 * i + 2;  // If left child is larger than root  if (left < N && arr[left]>arr[più grande]) più grande = sinistra;  // Se il bambino destro è più grande del più grande // finora if (right< N && arr[right]>arr[più grande]) più grande = destra;  // Scambia e continua l'heap // se root non è il più grande // Se il più grande non è root if (largest != i) { swap(&arr[i], &arr[largest]);  // Heapify ricorsivamente il // sottoalbero interessato heapify(arr, N, large);  } } // Funzione principale per eseguire l'heap sort void heapSort(int arr[], int N) { // Crea l'heap massimo per (int i = N / 2 - 1; i>= 0; i--) heapify(arr , N, i);  // Ordinamento dell'heap per (int i = N - 1; i>= 0; i--) { swap(&arr[0], &arr[i]);  // Heapify l'elemento root // per ottenere l'elemento più alto in // root di nuovo heapify(arr, i, 0);  } } // Una funzione di utilità per stampare un array di dimensione n void printArray(int arr[], int N) { for (int i = 0; i< N; i++)  printf('%d ', arr[i]);  printf('
'); } // Driver's code int main() {  int arr[] = { 12, 11, 13, 5, 6, 7 };  int N = sizeof(arr) / sizeof(arr[0]);  // Function call  heapSort(arr, N);  printf('Sorted array is
');  printArray(arr, N); } // This code is contributed by _i_plus_plus_.>
Giava 
// Java program for implementation of Heap Sort public class HeapSort {  public void sort(int arr[])  {  int N = arr.length;  // Build heap (rearrange array)  for (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i);  // Uno per uno estrae un elemento dall'heap for (int i = N - 1; i> 0; i--) { // Sposta la radice corrente alla fine int temp = arr[0];  arr[0] = arr[i];  arr[i] = temperatura;  // chiama max heapify sull'heap ridotto heapify(arr, i, 0);  } } // Per heapificare un sottoalbero con radice con il nodo i che è // un indice in arr[]. n è la dimensione dell'heap void heapify(int arr[], int N, int i) { int più grande = i; // Inizializza il più grande come root int l = 2 * i + 1; // sinistra = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // Se il figlio sinistro è più grande della radice if (l< N && arr[l]>arr[più grande]) più grande = l;  // Se il bambino destro è più grande del più grande finora se (r< N && arr[r]>arr[più grande]) più grande = r;  // Se il più grande non è root if (più grande!= i) { int swap = arr[i];  arr[i] = arr[più grande];  arr[più grande] = scambia;  // Heapify ricorsivamente il sottoalbero interessato heapify(arr, N, large);  } } /* Una funzione di utilità per stampare un array di dimensione n */ static void printArray(int arr[]) { int N = arr.length;  for (int i = 0; i< N; ++i)  System.out.print(arr[i] + ' ');  System.out.println();  }  // Driver's code  public static void main(String args[])  {  int arr[] = { 12, 11, 13, 5, 6, 7 };  int N = arr.length;  // Function call  HeapSort ob = new HeapSort();  ob.sort(arr);  System.out.println('Sorted array is');  printArray(arr);  } }>
C# 
// C# program for implementation of Heap Sort using System; public class HeapSort {  public void sort(int[] arr)  {  int N = arr.Length;  // Build heap (rearrange array)  for (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i);  // Uno per uno estrae un elemento dall'heap for (int i = N - 1; i> 0; i--) { // Sposta la radice corrente alla fine int temp = arr[0];  arr[0] = arr[i];  arr[i] = temperatura;  // chiama max heapify sull'heap ridotto heapify(arr, i, 0);  } } // Per heapificare un sottoalbero con radice con il nodo i che è // un indice in arr[]. n è la dimensione dell'heap void heapify(int[] arr, int N, int i) { int più grande = i; // Inizializza il più grande come root int l = 2 * i + 1; // sinistra = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // Se il figlio sinistro è più grande della radice if (l< N && arr[l]>arr[più grande]) più grande = l;  // Se il bambino destro è più grande del più grande finora se (r< N && arr[r]>arr[più grande]) più grande = r;  // Se il più grande non è root if (più grande!= i) { int swap = arr[i];  arr[i] = arr[più grande];  arr[più grande] = scambia;  // Heapify ricorsivamente il sottoalbero interessato heapify(arr, N, large);  } } /* Una funzione di utilità per stampare un array di dimensione n */ static void printArray(int[] arr) { int N = arr.Length;  for (int i = 0; i< N; ++i)  Console.Write(arr[i] + ' ');  Console.Read();  }  // Driver's code  public static void Main()  {  int[] arr = { 12, 11, 13, 5, 6, 7 };  int N = arr.Length;  // Function call  HeapSort ob = new HeapSort();  ob.sort(arr);  Console.WriteLine('Sorted array is');  printArray(arr);  } } // This code is contributed // by Akanksha Rai(Abby_akku)>
Javascript 
// JavaScript program for implementation // of Heap Sort  function sort( arr)  {  var N = arr.length;  // Build heap (rearrange array)  for (var i = Math.floor(N / 2) - 1; i>= 0; i--) heapify(arr, N, i);  // Estrai uno per uno un elemento dall'heap for (var i = N - 1; i> 0; i--) { // Sposta la radice corrente alla fine var temp = arr[0];  arr[0] = arr[i];  arr[i] = temperatura;  // chiama max heapify sull'heap ridotto heapify(arr, i, 0);  } } // Per heapificare un sottoalbero con radice con il nodo i che è // un indice in arr[]. n è la dimensione della funzione heap heapify(arr, N, i) { var più grande = i; // Inizializza il più grande come root var l = 2 * i + 1; // sinistra = 2*i + 1 var r = 2 * i + 2; // right = 2*i + 2 // Se il figlio sinistro è più grande della radice if (l< N && arr[l]>arr[più grande]) più grande = l;  // Se il bambino destro è più grande del più grande finora se (r< N && arr[r]>arr[più grande]) più grande = r;  // Se il più grande non è root if (largest != i) { var swap = arr[i];  arr[i] = arr[più grande];  arr[più grande] = scambia;  // Heapify ricorsivamente il sottoalbero interessato heapify(arr, N, large);  } } /* Una funzione di utilità per stampare un array di dimensione n */ function printArray(arr) { var N = arr.length;  per (var i = 0; i< N; ++i)  document.write(arr[i] + ' ');    }  var arr = [12, 11, 13, 5, 6, 7];  var N = arr.length;  sort(arr);  document.write( 'Sorted array is');  printArray(arr, N); // This code is contributed by SoumikMondal>
PHP 
 // Php program for implementation of Heap Sort // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap function heapify(&$arr, $N, $i) { $largest = $i; // Initialize largest as root $l = 2*$i + 1; // left = 2*i + 1 $r = 2*$i + 2; // right = 2*i + 2 // If left child is larger than root if ($l < $N && $arr[$l]>$arr[$più grande]) $più grande = $l; // Se il figlio destro è più grande del più grande finora if ($r< $N && $arr[$r]>$arr[$più grande]) $più grande = $r; // Se il più grande non è root if ($più grande!= $i) { $swap = $arr[$i]; $arr[$i] = $arr[$più grande]; $arr[$più grande] = $scambio; // Heapify ricorsivamente il sottoalbero interessato heapify($arr, $N, $largest); } } // funzione principale per eseguire la funzione di ordinamento dell'heap heapSort(&$arr, $N) { // Costruisci l'heap (riorganizza l'array) per ($i = $N / 2 - 1; $i>= 0; $i- -) heapify($arr, $N, $i); // Estrai uno per uno un elemento dall'heap for ($i = $N-1; $i> 0; $i--) { // Sposta la radice corrente alla fine $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $temp; // chiama max heapify sull'heap ridotto heapify($arr, $i, 0); } } /* Una funzione di utilità per stampare un array di dimensione n */ function printArray(&$arr, $N) { for ($i = 0; $i< $N; ++$i) echo ($arr[$i].' ') ; } // Driver's program $arr = array(12, 11, 13, 5, 6, 7); $N = sizeof($arr)/sizeof($arr[0]); // Function call heapSort($arr, $N); echo 'Sorted array is ' . '
'; printArray($arr , $N); // This code is contributed by Shivi_Aggarwal ?>>
Python3 
# Python program for implementation of heap Sort # To heapify subtree rooted at index i. # n is size of heap def heapify(arr, N, i): largest = i # Initialize largest as root l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 # See if left child of root exists and is # greater than root if l < N and arr[largest] < arr[l]: largest = l # See if right child of root exists and is # greater than root if r < N and arr[largest] < arr[r]: largest = r # Change root, if needed if largest != i: arr[i], arr[largest] = arr[largest], arr[i] # swap # Heapify the root. heapify(arr, N, largest) # The main function to sort an array of given size def heapSort(arr): N = len(arr) # Build a maxheap. for i in range(N//2 - 1, -1, -1): heapify(arr, N, i) # One by one extract elements for i in range(N-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # swap heapify(arr, i, 0) # Driver's code if __name__ == '__main__': arr = [12, 11, 13, 5, 6, 7] # Function call heapSort(arr) N = len(arr) print('Sorted array is') for i in range(N): print('%d' % arr[i], end=' ') # This code is contributed by Mohit Kumra>
Produzione 
Sorted array is 5 6 7 11 12 13>

Analisi della complessità di Ordinamento heap

Complessità temporale: O(N logN)
Spazio ausiliario: O(log n), a causa dello stack di chiamate ricorsivo. Tuttavia, lo spazio ausiliario può essere O(1) per l'implementazione iterativa.

Punti importanti sull'ordinamento heap:

  • L'ordinamento dell'heap è un algoritmo sul posto.
  • La sua tipica implementazione non è stabile ma può essere resa stabile (Vedi Questo )
  • In genere 2-3 volte più lento di quanto ben implementato Ordinamento rapido . Il motivo della lentezza è la mancanza di località di riferimento.

Vantaggi dell'ordinamento heap:

  • Complessità temporale efficiente: L'Heap Sort ha una complessità temporale pari a O(n log n) in tutti i casi. Ciò lo rende efficiente per l'ordinamento di set di dati di grandi dimensioni. IL registro n Il fattore deriva dall'altezza dell'heap binario e garantisce che l'algoritmo mantenga buone prestazioni anche con un numero elevato di elementi.
  • Utilizzo della memoria - L'utilizzo della memoria può essere minimo (scrivendo un heapify() iterativo invece di uno ricorsivo). Quindi, a parte quanto necessario per contenere l'elenco iniziale degli elementi da ordinare, non necessita di spazio di memoria aggiuntivo per funzionare
  • Semplicità – È più semplice da comprendere rispetto ad altri algoritmi di ordinamento altrettanto efficienti perché non utilizza concetti informatici avanzati come la ricorsione.

Svantaggi dell'ordinamento heap:

  • Costoso : L'ordinamento dell'heap è costoso poiché le costanti sono più elevate rispetto all'ordinamento di tipo merge anche se la complessità temporale è O(n Log n) per entrambi.
  • Instabile : L'ordinamento dell'heap è instabile. Potrebbe riorganizzare l'ordine relativo.
  • Efficiente: L'ordinamento dell'heap non è molto efficiente quando si lavora con dati altamente complessi.

Domande frequenti relative all'ordinamento heap

Q1. Quali sono le due fasi di Heap Sort?

L'algoritmo di ordinamento dell'heap è costituito da due fasi. Nella prima fase, l'array viene convertito in un heap massimo. E nella seconda fase, l'elemento più alto viene rimosso (cioè quello alla radice dell'albero) e gli elementi rimanenti vengono utilizzati per creare un nuovo heap massimo.

Q2. Perché l'ordinamento dell'heap non è stabile?

L'algoritmo di ordinamento dell'heap non è un algoritmo stabile perché scambiamo arr[i] con arr[0] in heapSort() che potrebbe modificare l'ordine relativo delle chiavi equivalenti.

Q3. Heap Sort è un esempio dell'algoritmo Divide and Conquer?

L'ordinamento dell'heap lo è NON è affatto un algoritmo “Dividi e Impera”. Utilizza una struttura di dati heap per ordinare in modo efficiente il suo elemento e non un approccio divide et impera per ordinare gli elementi.

Q4. Quale algoritmo di ordinamento è migliore: Heap sort o Merge Sort?

vuoto 0

La risposta sta nel confronto tra la loro complessità temporale e le esigenze di spazio. L'ordinamento Unisci è leggermente più veloce dell'ordinamento Heap. Ma d'altra parte l'ordinamento per unione richiede memoria aggiuntiva. A seconda delle esigenze si deve scegliere quale utilizzare.

Q5. Perché l'ordinamento dell'heap è migliore dell'ordinamento della selezione?

L'ordinamento dell'heap è simile all'ordinamento della selezione, ma con un modo migliore per ottenere il massimo elemento. Sfrutta la struttura dei dati heap per ottenere l'elemento massimo in tempo costante