logo

TechCodeview

Heap Sort - Veiledninger for datastrukturer og algoritmer

Masse sortering er en sammenligningsbasert sorteringsteknikk basert på Binær haug data struktur. Det ligner på utvalg sortering hvor vi først finner minimumselementet og plasserer minimumselementet i begynnelsen. Gjenta den samme prosessen for de resterende elementene.

Algoritme for haugsortering

Følg ideen nedenfor for å løse problemet:



Konverter først arrayet til heap-datastruktur ved hjelp av heapify, så en etter en slett rotnoden til Max-heapen og erstatt den med den siste noden i heapen og heap deretter rotnoden til heapen. Gjenta denne prosessen til størrelsen på haugen er større enn 1.

  • Bygg en haug fra den gitte inndatamatrisen.
  • Gjenta følgende trinn til haugen inneholder bare ett element:
    • Bytt rotelementet til haugen (som er det største elementet) med det siste elementet i haugen.
    • Fjern det siste elementet av haugen (som nå er i riktig posisjon).
    • Heapify de resterende elementene i haugen.
  • Den sorterte matrisen oppnås ved å reversere rekkefølgen på elementene i input-matrisen.
Anbefalt problem Vennligst løs det på PRAKTISERING først, før du går videre til løsningen Løs problem

Detaljert bearbeiding av haugsortering

For å forstå haugsortering klarere, la oss ta en usortert matrise og prøve å sortere den ved hjelp av haugsortering.
Tenk på matrisen: arr[] = {4, 10, 3, 5, 1}.

Bygg komplett binært tre: Bygg et komplett binært tre fra matrisen.



Heapsorteringsalgoritme | Bygg komplett binært tre

awt java

Gjør om til maksimal haug: Etter det er oppgaven å konstruere et tre fra den usorterte matrisen og prøve å konvertere den til maks haug.

  • For å transformere en haug til en maks-heap, bør den overordnede noden alltid være større enn eller lik barnenodene
    • Her, i dette eksemplet, som overordnet node 4 er mindre enn barnenoden 10, bytt dem derfor for å bygge en maks-haug.
  • Nå, 4 som forelder er mindre enn barnet 5 , bytt deretter begge disse igjen og den resulterende haugen og matrisen skal være slik:

Heapsorteringsalgoritme | Max Heapify konstruerte binært tre



Utfør haugsortering: Fjern det maksimale elementet i hvert trinn (dvs. flytt det til endeposisjonen og fjern det) og vurder deretter de gjenværende elementene og transformer det til en maksimal haug.

  • Slett rotelementet (10) fra makshaugen. For å slette denne noden, prøv å bytte den med den siste noden, dvs. (1). Etter å ha fjernet rotelementet, heapify det igjen for å konvertere det til max heap.
    • Den resulterende haugen og arrayen skal se slik ut:

Heapsorteringsalgoritme | Fjern maksimum fra root og max heapify

gi nytt navn til katalogen linux
  • Gjenta trinnene ovenfor og det vil se slik ut:

Heapsorteringsalgoritme | Fjern neste maksimum fra root nad max heapify

  • Fjern nå roten (dvs. 3) igjen og utfør heapify.

Heapsorteringsalgoritme | Gjenta forrige trinn

  • Når roten er fjernet igjen, er den sortert. og den sorterte matrisen vil være som arr[] = {1, 3, 4, 5, 10} .

Heapsorteringsalgoritme | Endelig sortert array

Implementering av 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[størst]) største = l;  // Hvis høyre barn er større enn størst // så langt hvis (r< N && arr[r]>arr[størst]) største = r;  // Hvis største ikke er rot if (størst != i) { swap(arr[i], arr[størst]);  // Heapify rekursivt det berørte // sub-tree heapify(arr, N, størst);  } } // Hovedfunksjon for å gjøre heapsortering void heapSort(int arr[], int N) { // Bygg heap (omorganisere array) for (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i);  // En etter en trekke ut et element // fra heap for (int i = N - 1; i> 0; i--) { // Flytt gjeldende rot for å avslutte bytte(arr[0], arr[i]);  // ring max heapify på den reduserte heapify(arr, i, 0);  } } // En verktøyfunksjon for å skrive ut matrise med størrelse 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[størst]) største = venstre;  // Hvis høyre barn er større enn størst // så langt hvis (høyre< N && arr[right]>arr[størst]) største = høyre;  // Bytt og fortsett å heapifying // hvis root ikke er størst // Hvis største ikke er root if (størst != i) { swap(&arr[i], &arr[størst]);  // Heapify rekursivt det berørte // sub-tree heapify(arr, N, størst);  } } // Hovedfunksjon for å gjøre heap sort void heapSort(int arr[], int N) { // Bygg maks heap for (int i = N / 2 - 1; i>= 0; i--) heapify(arr , N, i);  // Heap sort for (int i = N - 1; i>= 0; i--) { swap(&arr[0], &arr[i]);  // Heapify root element // for å få høyeste element ved // root again heapify(arr, i, 0);  } } // En verktøyfunksjon for å skrive ut matrise med størrelse 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);  // En etter en trekke ut et element fra heap for (int i = N - 1; i> 0; i--) { // Flytt gjeldende rot til slutten int temp = arr[0];  arr[0] = arr[i];  arr[i] = temp;  // ring max heapify på den reduserte heapify(arr, i, 0);  } } // Å heapify et undertre med rot med node i som er // en indeks i arr[]. n er størrelsen på heap void heapify(int arr[], int N, int i) { int største = i; // Initialiser størst som rot int l = 2 * i + 1; // venstre = 2*i + 1 int r = 2 *i + 2; // høyre = 2*i + 2 // Hvis venstre barn er større enn roten hvis (l< N && arr[l]>arr[størst]) største = l;  // Hvis høyre barn er større enn størst så langt hvis (r< N && arr[r]>arr[størst]) største = r;  // Hvis største ikke er rot if (størst != i) { int swap = arr[i];  arr[i] = arr[størst];  arr[størst] = bytte;  // Heapify rekursivt det berørte undertreet heapify(arr, N, størst);  } } /* En verktøyfunksjon for å skrive ut array av størrelse 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);  // En etter en trekke ut et element fra heap for (int i = N - 1; i> 0; i--) { // Flytt gjeldende rot til slutten int temp = arr[0];  arr[0] = arr[i];  arr[i] = temp;  // ring max heapify på den reduserte heapify(arr, i, 0);  } } // Å heapify et undertre med rot med node i som er // en indeks i arr[]. n er størrelsen på heap void heapify(int[] arr, int N, int i) { int største = i; // Initialiser størst som rot int l = 2 * i + 1; // venstre = 2*i + 1 int r = 2 *i + 2; // høyre = 2*i + 2 // Hvis venstre barn er større enn roten hvis (l< N && arr[l]>arr[størst]) største = l;  // Hvis høyre barn er større enn størst så langt hvis (r< N && arr[r]>arr[størst]) største = r;  // Hvis største ikke er rot if (størst != i) { int swap = arr[i];  arr[i] = arr[størst];  arr[størst] = bytte;  // Heapify rekursivt det berørte undertreet heapify(arr, N, størst);  } } /* En verktøyfunksjon for å skrive ut array av størrelse 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);  // En etter en trekke ut et element fra heap for (var i = N - 1; i> 0; i--) { // Flytt gjeldende rot til slutten var temp = arr[0];  arr[0] = arr[i];  arr[i] = temp;  // ring max heapify på den reduserte heapify(arr, i, 0);  } } // For å heapify et undertre med rot med node i som er // en indeks i arr[]. n er størrelsen på heap-funksjonen heapify(arr, N, i) { var største = i; // Initialiser størst som rot var l = 2 * i + 1; // venstre = 2*i + 1 var r = 2 *i + 2; // høyre = 2*i + 2 // Hvis venstre barn er større enn roten hvis (l< N && arr[l]>arr[størst]) største = l;  // Hvis høyre barn er større enn størst så langt hvis (r< N && arr[r]>arr[størst]) største = r;  // Hvis største ikke er root if (størst != i) { var swap = arr[i];  arr[i] = arr[størst];  arr[størst] = bytte;  // Heapify rekursivt det berørte undertreet heapify(arr, N, størst);  } } /* En verktøyfunksjon for å skrive ut array av størrelse n */ function printArray(arr) { var N = arr.length;  for (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[$største]) $største = $l; // Hvis høyre barn er større enn størst så langt hvis ($r< $N && $arr[$r]>$arr[$største]) $største = $r; // Hvis største ikke er root if ($largest != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$største]; $arr[$largest] = $bytte; // Heapify rekursivt det berørte undertreet heapify($arr, $N, $størst); } } // hovedfunksjon for å gjøre haugsorteringsfunksjon heapSort(&$arr, $N) { // Bygg haug (omorganisere array) for ($i = $N / 2 - 1; $i>= 0; $i- -) heapify($arr, $N, $i); // En etter en trekke ut et element fra heap for ($i = $N-1; $i> 0; $i--) { // Flytt gjeldende rot til slutten $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $temp; // ring max heapify på den reduserte heapen heapify($arr, $i, 0); } } /* En verktøyfunksjon for å skrive ut array av størrelse 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>
Produksjon 
Sorted array is 5 6 7 11 12 13>

Kompleksitetsanalyse av Heap Sorter

Tidskompleksitet: O(N log N)
Hjelpeplass: O(log n), på grunn av den rekursive anropsstakken. Imidlertid kan hjelperom være O(1) for iterativ implementering.

Viktige punkter om haugsortering:

  • Heap-sortering er en algoritme på stedet.
  • Dens typiske implementering er ikke stabil, men kan gjøres stabil (se dette )
  • Typisk 2-3 ganger langsommere enn godt implementert QuickSort . Årsaken til tregheten er mangel på referanselokalitet.

Fordeler med haugsortering:

  • Effektiv tidskompleksitet: Heap Sort har en tidskompleksitet på O(n log n) i alle tilfeller. Dette gjør det effektivt for sortering av store datasett. De logg n faktor kommer fra høyden på den binære haugen, og den sikrer at algoritmen opprettholder god ytelse selv med et stort antall elementer.
  • Minnebruk - Minnebruken kan være minimal (ved å skrive en iterativ heapify() i stedet for en rekursiv). Så bortsett fra det som er nødvendig for å holde den første listen over elementer som skal sorteres, trenger den ingen ekstra minneplass for å fungere
  • Enkelhet – Den er enklere å forstå enn andre like effektive sorteringsalgoritmer fordi den ikke bruker avanserte datavitenskapelige konsepter som rekursjon.

Ulemper med haugsortering:

  • Kostbar : Heapsortering er kostbart ettersom konstantene er høyere sammenlignet med merge sort selv om tidskompleksiteten er O(n Log n) for begge.
  • Ustabil : Bunnsortering er ustabil. Det kan omorganisere den relative rekkefølgen.
  • Effektiv: Heap Sort er lite effektivt når du arbeider med svært komplekse data.

Ofte stilte spørsmål knyttet til haugsortering

Q1. Hva er de to fasene av haugsortering?

10 ml til unser

Heapsorteringsalgoritmen består av to faser. I den første fasen konverteres matrisen til en maks haug. Og i den andre fasen fjernes det høyeste elementet (dvs. det ved treroten) og de resterende elementene brukes til å lage en ny maksimal haug.

Q2. Hvorfor Heap Sort er ikke stabil?

Heap-sorteringsalgoritmen er ikke en stabil algoritme fordi vi bytter arr[i] med arr[0] i heapSort() som kan endre den relative rekkefølgen til de ekvivalente nøklene.

Q3. Er Heap Sort et eksempel på Divide and Conquer-algoritmen?

Heap sort er IKKE i det hele tatt en Divide and Conquer-algoritme. Den bruker en haugdatastruktur for å effektivt sortere elementet og ikke en del og hersk-tilnærming for å sortere elementene.

Q4. Hvilken sorteringsalgoritme er bedre – Heap-sortering eller Merge Sort?

konvertering fra streng til int i java

Svaret ligger i sammenligningen av deres tidskompleksitet og plassbehov. Merge-sorteringen er litt raskere enn Heap-sorteringen. Men på den annen side tar merge sort ekstra minne. Avhengig av kravet bør man velge hvilken som skal brukes.

Q5. Hvorfor er haugsortering bedre enn utvalgssortering?

Heap-sortering ligner på utvalgssortering, men med en bedre måte å få maksimalt element på. Den drar fordel av haugdatastrukturen for å få det maksimale elementet på konstant tid