logo

TechCodeview

Heap Sort - Tutorials d'estructures de dades i algorismes

Classificació de pila és una tècnica d'ordenació basada en la comparació Munt binari estructura de dades. És similar a la ordenació de selecció on primer trobem l'element mínim i col·loquem l'element mínim al principi. Repetiu el mateix procés per als elements restants.

Algoritme d'ordenació de pila

Per resoldre el problema seguiu la idea següent:

Primer convertiu la matriu a l'estructura de dades de l'munt mitjançant heapify, després suprimiu un per un el node arrel del Max-heap i substituïu-lo amb l'últim node del munt i, a continuació, amunteu l'arrel del munt. Repetiu aquest procés fins que la mida del munt sigui superior a 1.



  • Creeu un munt a partir de la matriu d'entrada donada.
  • Repetiu els passos següents fins que la pila contingui només un element:
    • Canvia l'element arrel del munt (que és l'element més gran) amb l'últim element del munt.
    • Traieu l'últim element del munt (que ara està a la posició correcta).
    • Amuntega els elements restants del munt.
  • La matriu ordenada s'obté invertint l'ordre dels elements de la matriu d'entrada.
Problema recomanat Si us plau, solucioneu-lo primer a PRÀCTICA, abans de passar a la solució Resoldre el problema

Treball detallat de Heap Sort

Per entendre més clarament l'ordenació de la pila, agafem una matriu sense ordenar i provem d'ordenar-la mitjançant l'ordenació de l'emmagatzematge.
Considereu la matriu: arr[] = {4, 10, 3, 5, 1}.

Construeix un arbre binari complet: Construeix un arbre binari complet a partir de la matriu.

Algorisme d'ordenació de pila | Construeix un arbre binari complet

Transformar en un munt màxim: Després d'això, la tasca és construir un arbre a partir d'aquesta matriu no ordenada i intentar convertir-lo munt màxim.

  • Per transformar un munt en un munt màxim, el node pare sempre ha de ser més gran o igual que els nodes secundaris.
    • Aquí, en aquest exemple, com el node pare 4 és més petit que el node fill 10, per tant, intercanvieu-los per crear un munt màxim.
  • Ara, 4 com a pare és més petit que el fill 5 , per tant, intercanvieu tots dos de nou i el munt i la matriu resultants haurien de ser així:

Algorisme d'ordenació de pila | Max Heapify va construir un arbre binari

Feu l'ordenació de pila: Traieu l'element màxim a cada pas (és a dir, moveu-lo a la posició final i traieu-lo) i, a continuació, considereu els elements restants i transformeu-lo en un munt màxim.

  • Suprimeix l'element arrel (10) del munt màxim. Per eliminar aquest node, proveu d'intercanviar-lo amb l'últim node, és a dir. (1). Després d'eliminar l'element arrel, torneu a amuntegar-lo per convertir-lo en un munt màxim.
    • El munt i la matriu resultants haurien de ser així:

Algorisme d'ordenació de pila | Elimina el màxim de l'arrel i el màxim heapify

  • Repetiu els passos anteriors i quedarà com el següent:

Algorisme d'ordenació de pila | Elimineu el següent màxim de l'arrel i l'heapify màxim

  • Ara traieu l'arrel (és a dir, 3) de nou i feu heapify.

Algorisme d'ordenació de pila | Repetiu el pas anterior

estat git
  • Ara, quan s'elimina l'arrel una vegada més, s'ordena. i la matriu ordenada serà com arr[] = {1, 3, 4, 5, 10} .

Algorisme d'ordenació de pila | Matriu ordenat final

Implementació de 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[més gran]) més gran = l;  // Si el fill dret és més gran que el més gran // fins ara si (r< N && arr[r]>arr[més gran]) més gran = r;  // Si el més gran no és arrel if (més gran != i) { swap(arr[i], arr[més gran]);  // Heapify recursivament el // subarbre afectat heapify(arr, N, major);  } } // Funció principal per fer l'ordenació de pila void heapSort(int arr[], int N) { // Construeix heap (reordena la matriu) per a (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i);  // Un per un extreu un element // de l'heap per (int i = N - 1; i> 0; i--) { // Mou l'arrel actual per acabar l'intercanvi (arr[0], arr[i]);  // crida a max heapify a l'heap reduït (arr, i, 0);  } } // Una funció d'utilitat per imprimir una matriu de mida 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[més gran]) més gran = esquerra;  // Si el fill dret és més gran que el més gran // fins ara si (dreta< N && arr[right]>arr[més gran]) més gran = dret;  // Canviar i continuar acumulant // si l'arrel no és més gran // Si el més gran no és l'arrel if (la més gran != i) { swap(&arr[i], &arr[més gran]);  // Heapify recursivament el // subarbre afectat heapify(arr, N, major);  } } // Funció principal per fer l'ordenació de la pila void heapSort(int arr[], int N) { // Construeix un munt màxim per a (int i = N / 2 - 1; i>= 0; i--) heapify (arr , N, i);  // Ordenació de pila per a (int i = N - 1; i>= 0; i--) { swap(&arr[0], &arr[i]);  // Heapify element arrel // per obtenir l'element més alt a // arrel de nou heapify(arr, i, 0);  } } // Una funció d'utilitat per imprimir una matriu de mida 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_.>
Java 
// 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);  // Un per un extreu un element de l'heap per a (int i = N - 1; i> 0; i--) { // Mou l'arrel actual al final int temp = arr[0];  arr[0] = arr[i];  arr[i] = temp;  // crida a max heapify a l'heap reduït (arr, i, 0);  } } // Per acumular un subarbre arrelat amb el node i que // és un índex a arr[]. n és la mida de l'heap void heapify(int arr[], int N, int i) { int major = i; // Inicialitzar el més gran com a arrel int l = 2 * i + 1; // esquerra = 2*i + 1 int r = 2 * i + 2; // dreta = 2*i + 2 // Si el fill esquerre és més gran que l'arrel si (l< N && arr[l]>arr[més gran]) més gran = l;  // Si el fill dret és més gran que el més gran fins ara si (r< N && arr[r]>arr[més gran]) més gran = r;  // Si el més gran no és root if (més gran != i) { int swap = arr[i];  arr[i] = arr[més gran];  arr[més gran] = intercanviar;  // Heapify recursivament el subarbre afectat heapify(arr, N, major);  } } /* Una funció d'utilitat per imprimir una matriu de mida n */ static void printArray(int arr[]) { int N = arr.length;  per (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);  // Un per un extreu un element de l'heap per a (int i = N - 1; i> 0; i--) { // Mou l'arrel actual al final int temp = arr[0];  arr[0] = arr[i];  arr[i] = temp;  // crida a max heapify a l'heap reduït (arr, i, 0);  } } // Per acumular un subarbre arrelat amb el node i que // és un índex a arr[]. n és la mida de l'heap void heapify(int[] arr, int N, int i) { int major = i; // Inicialitzar el més gran com a arrel int l = 2 * i + 1; // esquerra = 2*i + 1 int r = 2 * i + 2; // dreta = 2*i + 2 // Si el fill esquerre és més gran que l'arrel si (l< N && arr[l]>arr[més gran]) més gran = l;  // Si el fill dret és més gran que el més gran fins ara si (r< N && arr[r]>arr[més gran]) més gran = r;  // Si el més gran no és root if (més gran != i) { int swap = arr[i];  arr[i] = arr[més gran];  arr[més gran] = intercanviar;  // Heapify recursivament el subarbre afectat heapify(arr, N, major);  } } /* Una funció d'utilitat per imprimir una matriu de mida n */ static void printArray(int[] arr) { int N = arr.Length;  per (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);  // Un per un extreu un element de l'heap per a (var i = N - 1; i> 0; i--) { // Mou l'arrel actual al final var temp = arr[0];  arr[0] = arr[i];  arr[i] = temp;  // crida a max heapify a l'heap reduït (arr, i, 0);  } } // Per acumular un subarbre arrelat amb el node i que // és un índex a arr[]. n és la mida de la funció heap heapify(arr, N, i) { var més gran = i; // Inicialitzar més gran com a arrel var l = 2 * i + 1; // esquerra = 2*i + 1 var r = 2 * i + 2; // dreta = 2*i + 2 // Si el fill esquerre és més gran que l'arrel si (l< N && arr[l]>arr[més gran]) més gran = l;  // Si el fill dret és més gran que el més gran fins ara si (r< N && arr[r]>arr[més gran]) més gran = r;  // Si el més gran no és arrel if (més gran != i) { var swap = arr[i];  arr[i] = arr[més gran];  arr[més gran] = intercanviar;  // Heapify recursivament el subarbre afectat heapify(arr, N, major);  } } /* Una funció d'utilitat per imprimir una matriu de mida 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[$més gran]) $més gran = $l; // Si el fill dret és més gran que el més gran fins ara si ($r< $N && $arr[$r]>$arr[$més gran]) $més gran = $r; // Si el més gran no és arrel if ($més gran != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$més gran]; $arr[$més gran] = $canvi; // Heapify recursivament el subarbre afectat heapify($arr, $N, $largest); } } // funció principal per fer la funció d'ordenació heapSort(&$arr, $N) { // Construeix un munt (reordena la matriu) per a ($i = $N / 2 - 1; $i>= 0; $i- -) heapify($arr, $N, $i); // Un per un extreu un element de l'heap per ($i = $N-1; $i> 0; $i--) { // Mou l'arrel actual per acabar $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $temp; // crida a max heapify a l'heap reduït heapify($arr, $i, 0); } } /* Una funció d'utilitat per imprimir una matriu de mida n */ function printArray(&$arr, $N) { per ($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 ?>>
Python 3 
# 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>
Sortida 
Sorted array is 5 6 7 11 12 13>

Anàlisi de la complexitat Ordenació de pila

Complexitat temporal: O(N log N)
Espai auxiliar: O(log n), a causa de la pila de trucades recursives. Tanmateix, l'espai auxiliar pot ser O(1) per a la implementació iterativa.

Punts importants sobre Heap Sort:

  • L'ordenació de pila és un algorisme in situ.
  • La seva implementació típica no és estable, però es pot fer estable (vegeu això )
  • Normalment 2-3 vegades més lent que ben implementat QuickSort . El motiu de la lentitud és la manca de localitat de referència.

Avantatges de Heap Sort:

  • Complexitat de temps eficient: Heap Sort té una complexitat temporal de O(n log n) en tots els casos. Això fa que sigui eficient per ordenar grans conjunts de dades. El registre n El factor prové de l'alçada del munt binari i assegura que l'algorisme mantingui un bon rendiment fins i tot amb un gran nombre d'elements.
  • Ús de memòria - L'ús de memòria pot ser mínim (escrivint un heapify() iteratiu en lloc d'un recursiu). Així, a part del que és necessari per contenir la llista inicial d'elements a ordenar, no necessita espai de memòria addicional per funcionar
  • Senzillesa - És més senzill d'entendre que altres algorismes d'ordenació igualment eficients perquè no utilitza conceptes informàtics avançats com la recursivitat.

Desavantatges de Heap Sort:

  • Costós : L'ordenació de pila és costosa, ja que les constants són més elevades en comparació amb l'ordenació de combinació, fins i tot si la complexitat temporal és O(n Log n) per a tots dos.
  • Inestable : L'ordenació de pila és inestable. Podria reordenar l'ordre relatiu.
  • Eficient: Heap Sort no és gaire eficient quan es treballa amb dades molt complexes.

Preguntes freqüents relacionades amb Heap Sort

Q1. Quines són les dues fases de Heap Sort?

L'algorisme d'ordenació de pila consta de dues fases. En la primera fase, la matriu es converteix en un munt màxim. I en la segona fase, s'elimina l'element més alt (és a dir, el de l'arrel de l'arbre) i els elements restants s'utilitzen per crear un nou munt màxim.

Madhubala

P2. Per què Heap Sort no és estable?

L'algorisme d'ordenació de pila no és un algorisme estable perquè intercanviem arr[i] amb arr[0] a heapSort() que podria canviar l'ordre relatiu de les claus equivalents.

P3. Heap Sort és un exemple de l'algorisme Divide and Conquer?

L'ordenació de pila és NO en absolut un algorisme Divide and Conquer. Utilitza una estructura de dades de pila per ordenar el seu element de manera eficient i no un enfocament de dividir i conquerir per ordenar els elements.

P4. Quin algorisme d'ordenació és millor: ordenació de pila o ordenació de combinació?

La resposta rau en la comparació de la seva complexitat temporal i els requisits d'espai. L'ordenació Fusiona és una mica més ràpida que l'ordenació Heap. Però, d'altra banda, l'ordenació de combinació requereix més memòria. Depenent del requisit, s'ha de triar quin utilitzar.

P5. Per què és millor l'ordenació munt que l'ordenació per selecció?

L'ordenació de pila és similar a l'ordenació de selecció, però amb una millor manera d'obtenir l'element màxim. Aprofita l'estructura de dades d'heap per obtenir el màxim d'elements en temps constant