Sortare grămadă este o tehnică de sortare bazată pe comparație bazată pe Heap binar structură de date. Este similar cu sortare de selecție unde găsim mai întâi elementul minim și plasăm elementul minim la început. Repetați același proces pentru elementele rămase.
Algoritmul Heap Sort
Pentru a rezolva problema urmați ideea de mai jos:
Problemă recomandată Vă rugăm să o rezolvați mai întâi pe PRACTICE, înainte de a trece la soluția Rezolvare ProblemăMai întâi convertiți matricea în structură de date heap utilizând heapify, apoi ștergeți unul câte unul nodul rădăcină al heap-ului Max și înlocuiți-l cu ultimul nod din heap și apoi heapify rădăcina heap-ului. Repetați acest proces până când dimensiunea grămezii este mai mare de 1.
sumator plin
- Construiți un heap din matricea de intrare dată.
- Repetați următorii pași până când grămada conține un singur element:
- Schimbați elementul rădăcină al heap-ului (care este cel mai mare element) cu ultimul element al heap-ului.
- Scoateți ultimul element al mormanului (care este acum în poziția corectă).
- Îngrămădiți elementele rămase din grămada.
- Matricea sortată se obține prin inversarea ordinii elementelor din tabloul de intrare.
Funcționare detaliată a sortării heap
Pentru a înțelege mai clar sortarea heap, să luăm o matrice nesortată și să încercăm să o sortăm folosind heap sort.
Luați în considerare tabloul: arr[] = {4, 10, 3, 5, 1}.Construiți arbore binar complet: Construiți un arbore binar complet din matrice.
Algoritm de sortare heap | Construiește arbore binar complet
Transformați în grămada maximă: După aceea, sarcina este să construiești un arbore din acea matrice nesortată și să încerci să-l transformi în grămada maximă.
- Pentru a transforma un heap într-un max-heap, nodul părinte ar trebui să fie întotdeauna mai mare sau egal cu nodurile secundare
- Aici, în acest exemplu, ca nod părinte 4 este mai mic decât nodul copil 10, astfel, schimbați-le pentru a construi un max-heap.
- Acum, 4 ca parinte este mai mic decat copilul 5 , astfel schimbați din nou ambele, iar heap-ul și matricea rezultate ar trebui să fie așa:
Algoritm de sortare heap | Arborele binar construit de Max Heapify
Efectuați sortarea heap: Eliminați elementul maxim în fiecare pas (adică, mutați-l în poziția finală și eliminați-l) și apoi luați în considerare elementele rămase și transformați-l într-o grămadă maximă.
- Ștergeți elementul rădăcină (10) din grămada maximă. Pentru a șterge acest nod, încercați să-l schimbați cu ultimul nod, adică (1). După ce eliminați elementul rădăcină, îngrămați-l din nou pentru a-l converti în heap maxim.
- Heap-ul și matricea rezultate ar trebui să arate astfel:
Algoritm de sortare heap | Eliminați maximum din rădăcină și max heapify
- Repetați pașii de mai sus și va arăta astfel:
Algoritm de sortare heap | Eliminați următorul maxim din rădăcină și heapify maxim
sfoară prea lungă
- Acum eliminați rădăcina (adică 3) din nou și efectuați heapify.
Algoritm de sortare heap | Repetați pasul anterior
- Acum, când rădăcina este îndepărtată din nou, este sortată. iar matricea sortată va fi ca arr[] = {1, 3, 4, 5, 10} .
Algoritm de sortare heap | Matrice sortată finală
Implementarea 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[mai mare]) cel mai mare = l; // Dacă copilul drept este mai mare decât cel mai mare // până acum dacă (r< N && arr[r]>arr[cel mai mare]) cel mai mare = r; // Dacă cel mai mare nu este rădăcină if (mai mare != i) { swap(arr[i], arr[mai mare]); // Heapify recursiv afectat // sub-arborele heapify(arr, N, cel mai mare); } } // Funcția principală de sortare heap void heapSort(int arr[], int N) { // Construiți heap (rearanjare matrice) pentru (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // Extrage unul câte unul un element // din heap for (int i = N - 1; i> 0; i--) { // Mută rădăcina curentă pentru a termina swap(arr[0], arr[i]); // apelează max heapify pe heap-ul redus heapify(arr, i, 0); } } // O funcție utilitar pentru a tipări o matrice de dimensiune 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[mai mare]) cel mai mare = stânga; // Dacă copilul drept este mai mare decât cel mai mare // până acum dacă (dreapta< N && arr[right]>arr[mai mare]) cel mai mare = dreapta; // Schimbați și continuați să acumulați // dacă rădăcina nu este cea mai mare // Dacă cea mai mare nu este rădăcină if (mai mare != i) { swap(&arr[i], &arr[mai mare]); // Heapify recursiv afectat // sub-arborele heapify(arr, N, cel mai mare); } } // Funcția principală pentru sortarea heap void heapSort(int arr[], int N) { // Construiți heap maxim pentru (int i = N / 2 - 1; i>= 0; i--) heapify(arr , N, i); // Sortare grămadă pentru (int i = N - 1; i>= 0; i--) { swap(&arr[0], &arr[i]); // Heapify element rădăcină // pentru a obține cel mai înalt element la // rădăcină din nou heapify(arr, i, 0); } } // O funcție utilitar pentru a tipări o matrice de dimensiune 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); // Extrageți unul câte unul un element din heap for (int i = N - 1; i> 0; i--) { // Mută rădăcina curentă la final int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // apelează max heapify pe heap-ul redus heapify(arr, i, 0); } } // Pentru a îngrămădi un subarboresc înrădăcinat cu nodul i care este // un index în arr[]. n este dimensiunea heap void heapify(int arr[], int N, int i) { int cea mai mare = i; // Inițializează cel mai mare ca rădăcină int l = 2 * i + 1; // stânga = 2*i + 1 int r = 2 * i + 2; // dreapta = 2*i + 2 // Dacă copilul din stânga este mai mare decât rădăcina dacă (l< N && arr[l]>arr[mai mare]) cel mai mare = l; // Dacă copilul drept este mai mare decât cel mai mare de până acum dacă (r< N && arr[r]>arr[cel mai mare]) cel mai mare = r; // Dacă cel mai mare nu este rădăcină if (mai mare != i) { int swap = arr[i]; arr[i] = arr[cel mai mare]; arr[cel mai mare] = swap; // Heapify recursiv sub-arborele afectat heapify(arr, N, cel mai mare); } } /* O funcție utilitar pentru a tipări o matrice de dimensiune n */ static void printArray(int arr[]) { int N = arr.length; pentru (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); // Extrageți unul câte unul un element din heap for (int i = N - 1; i> 0; i--) { // Mută rădăcina curentă la final int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // apelează max heapify pe heap-ul redus heapify(arr, i, 0); } } // Pentru a îngrămădi un subarboresc înrădăcinat cu nodul i care este // un index în arr[]. n este dimensiunea heap void heapify(int[] arr, int N, int i) { int cea mai mare = i; // Inițializează cel mai mare ca rădăcină int l = 2 * i + 1; // stânga = 2*i + 1 int r = 2 * i + 2; // dreapta = 2*i + 2 // Dacă copilul din stânga este mai mare decât rădăcina dacă (l< N && arr[l]>arr[mai mare]) cel mai mare = l; // Dacă copilul drept este mai mare decât cel mai mare de până acum dacă (r< N && arr[r]>arr[cel mai mare]) cel mai mare = r; // Dacă cel mai mare nu este rădăcină if (mai mare != i) { int swap = arr[i]; arr[i] = arr[cel mai mare]; arr[cel mai mare] = swap; // Heapify recursiv sub-arborele afectat heapify(arr, N, cel mai mare); } } /* O funcție utilitar pentru a tipări o matrice de dimensiune n */ static void printArray(int[] arr) { int N = arr.Length; pentru (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); // Extrageți unul câte unul un element din heap for (var i = N - 1; i> 0; i--) { // Mută rădăcina curentă la final var temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // apelează max heapify pe heap-ul redus heapify(arr, i, 0); } } // Pentru a îngrămădi un subarboresc înrădăcinat cu nodul i care este // un index în arr[]. n este dimensiunea funcției heap heapify(arr, N, i) { var cea mai mare = i; // Inițializează cel mai mare ca rădăcină var l = 2 * i + 1; // stânga = 2*i + 1 var r = 2 * i + 2; // dreapta = 2*i + 2 // Dacă copilul din stânga este mai mare decât rădăcina dacă (l< N && arr[l]>arr[mai mare]) cel mai mare = l; // Dacă copilul drept este mai mare decât cel mai mare de până acum dacă (r< N && arr[r]>arr[cel mai mare]) cel mai mare = r; // Dacă cel mai mare nu este rădăcină if (mai mare != i) { var swap = arr[i]; arr[i] = arr[cel mai mare]; arr[cel mai mare] = swap; // Heapify recursiv sub-arborele afectat heapify(arr, N, cel mai mare); } } /* O funcție utilitar pentru a tipări o matrice de dimensiunea n */ function printArray(arr) { var N = arr.length; pentru (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[$mai mare]) $mai mare = $l; // Dacă copilul drept este mai mare decât cel mai mare de până acum dacă ($r< $N && $arr[$r]>$arr[$mai mare]) $mai mare = $r; // Dacă cel mai mare nu este rădăcină if ($mai mare != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$mai mare]; $arr[$mai mare] = $swap; // Heapify recursiv sub-arborele afectat heapify($arr, $N, $largest); } } // funcția principală pentru a face funcția de sortare heapSort(&$arr, $N) { // Construiește heap (rearanjare matrice) pentru ($i = $N / 2 - 1; $i>= 0; $i- -) heapify($arr, $N, $i); // Extrageți unul câte unul un element din heap pentru ($i = $N-1; $i> 0; $i--) { // Mută rădăcina curentă la final $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $temp; // apelează max heapify pe heap-ul redus heapify($arr, $i, 0); } } /* O funcție utilitar pentru a tipări o matrice de dimensiunea n */ function printArray(&$arr, $N) { pentru ($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 Ieșire
Sorted array is 5 6 7 11 12 13>
Analiza complexității Sortare grămadă
Complexitatea timpului: O(N log N)
Spațiu auxiliar: O(log n), datorită stivei de apeluri recursive. Cu toate acestea, spațiul auxiliar poate fi O(1) pentru implementare iterativă.
Puncte importante despre Heap Sort:
- Sortarea heap este un algoritm pe loc.
- Implementarea sa tipică nu este stabilă, dar poate fi stabilită (vezi acest )
- De obicei, de 2-3 ori mai lent decât bine implementat Sortare rapida . Motivul încetinirii este lipsa localității de referință.
Avantajele sortării heap:
- Complexitatea timpului eficient: Heap Sort are o complexitate de timp de O(n log n) în toate cazurile. Acest lucru îl face eficient pentru sortarea seturi de date mari. The jurnal n factorul provine din înălțimea heap-ului binar și asigură că algoritmul menține o performanță bună chiar și cu un număr mare de elemente.
- Folosirea memoriei - Utilizarea memoriei poate fi minimă (prin scrierea unui heapify() iterativ în loc de unul recursiv). Deci, în afară de ceea ce este necesar pentru a păstra lista inițială a elementelor de sortat, nu are nevoie de spațiu de memorie suplimentar pentru a funcționa
- Simplitate - Este mai simplu de înțeles decât alți algoritmi de sortare la fel de eficienți, deoarece nu utilizează concepte avansate de informatică, cum ar fi recursiunea.
Dezavantajele sortării heap:
- Costitor : Sortarea heap este costisitoare, deoarece constantele sunt mai mari în comparație cu sortarea prin îmbinare chiar dacă complexitatea timpului este O(n Log n) pentru ambele.
- Instabil : sortarea grămezilor este instabilă. Ar putea rearanja ordinea relativă.
- Eficient: Sortarea heap nu este foarte eficientă atunci când lucrați cu date foarte complexe.
Întrebări frecvente legate de Heap Sort
Î1. Care sunt cele două faze ale Heap Sort?
Algoritmul de sortare heap constă din două faze. În prima fază, matricea este convertită într-un heap maxim. Și în a doua fază, elementul cel mai înalt este eliminat (adică cel de la rădăcina copacului) și elementele rămase sunt folosite pentru a crea un nou heap maxim.
Q2. De ce Heap Sort nu este stabil?
Algoritmul de sortare heap nu este un algoritm stabil, deoarece schimbăm arr[i] cu arr[0] în heapSort() care ar putea schimba ordonarea relativă a cheilor echivalente.
Q3. Heap Sort este un exemplu al algoritmului Divide and Conquer?
Sortarea grămadă este NU deloc un algoritm Divide and Conquer. Folosește o structură de date heap pentru a-și sorta eficient elementul și nu o abordare de tip divide and cuquer pentru sortarea elementelor.
Î4. Ce algoritm de sortare este mai bun – Sortare în grămada sau Sortare prin îmbinare?
comanda de instalare npm
Răspunsul constă în compararea complexității lor în timp și a cerințelor de spațiu. Sortarea Merge este puțin mai rapidă decât sortarea Heap. Dar, pe de altă parte, sortarea prin îmbinare necesită memorie suplimentară. În funcție de cerință, trebuie să alegeți pe care să o utilizați.
Î5. De ce sortarea în grămada este mai bună decât sortarea prin selecție?
Sortarea heap este similară cu sortarea prin selecție, dar cu o modalitate mai bună de a obține elementul maxim. Profită de structura de date heap pentru a obține elementul maxim în timp constant