În acest articol, vom discuta despre algoritmul Heapsort. Sortarea heap procesează elementele creând min-heap sau max-heap folosind elementele matricei date. Min-heap sau max-heap reprezintă ordonarea matricei în care elementul rădăcină reprezintă elementul minim sau maxim al matricei.

Sortarea heap efectuează, practic, recursiv două operații principale -

• Construiți un heap H, folosind elementele matricei.
• Ștergeți în mod repetat elementul rădăcină al heap-ului format în 1^Sffază.

Înainte de a afla mai multe despre sortarea heap, să vedem mai întâi o scurtă descriere a Morman.

Ce este o grămadă?

O grămadă este un arbore binar complet, iar arborele binar este un arbore în care nodul poate avea maximum doi copii. Un arbore binar complet este un arbore binar în care toate nivelurile, cu excepția ultimului nivel, adică nodul frunză, ar trebui să fie complet umplute, iar toate nodurile ar trebui să fie justificate la stânga.

Ce este sortarea mormanului?

Heapsort este un algoritm de sortare popular și eficient. Conceptul de sortare heap este de a elimina elementele unul câte unul din partea heap a listei și apoi de a le insera în partea sortată a listei.

Heapsort este algoritmul de sortare in loc.

k algoritm de grupare

Acum, să vedem algoritmul de sortare heap.

Algoritm

 HeapSort(arr) BuildMaxHeap(arr) for i = length(arr) to 2 swap arr[1] with arr[i] heap_size[arr] = heap_size[arr] ? 1 MaxHeapify(arr,1) End 

BuildMaxHeap(arr)

 BuildMaxHeap(arr) heap_size(arr) = length(arr) for i = length(arr)/2 to 1 MaxHeapify(arr,i) End 

MaxHeapify(arr,i)

 MaxHeapify(arr,i) L = left(i) R = right(i) if L ? heap_size[arr] and arr[L] > arr[i] largest = L else largest = i if R ? heap_size[arr] and arr[R] > arr[largest] largest = R if largest != i swap arr[i] with arr[largest] MaxHeapify(arr,largest) End 

Funcționarea algoritmului de sortare Heap

Acum, să vedem funcționarea algoritmului Heapsort.

În sortarea grămezilor, practic, sunt două faze implicate în sortarea elementelor. Folosind algoritmul de sortare heap, acestea sunt după cum urmează -

• Primul pas include crearea unui heap prin ajustarea elementelor matricei.
• După crearea heap-ului, acum eliminați elementul rădăcină al heap-ului în mod repetat, deplasându-l la sfârșitul matricei, apoi stocați structura heap-ului cu elementele rămase.

Acum să vedem în detaliu funcționarea sortării heap folosind un exemplu. Pentru a înțelege mai clar, să luăm o matrice nesortată și să încercăm să o sortăm folosind sortarea grămadă. Va face explicația mai clară și mai ușoară.

În primul rând, trebuie să construim un heap din matricea dată și să îl convertim în heap maxim.

După conversia heap-ului dat în heap maxim, elementele matricei sunt -

În continuare, trebuie să ștergem elementul rădăcină (89) din grămada maximă. Pentru a șterge acest nod, trebuie să-l schimbăm cu ultimul nod, adică. (unsprezece). După ștergerea elementului rădăcină, trebuie din nou să-l îngrămădim pentru a-l converti în heap maxim.

După schimbarea elementului de matrice 89 cu unsprezece, și transformând heap-ul în max-heap, elementele matricei sunt -

În pasul următor, din nou, trebuie să ștergem elementul rădăcină (81) din grămada maximă. Pentru a șterge acest nod, trebuie să-l schimbăm cu ultimul nod, adică. (54). După ștergerea elementului rădăcină, trebuie din nou să-l îngrămădim pentru a-l converti în heap maxim.

După schimbarea elementului de matrice 81 cu 54 și transformând heap-ul în max-heap, elementele matricei sunt -

În pasul următor, trebuie să ștergem elementul rădăcină (76) din grămada maximă din nou. Pentru a șterge acest nod, trebuie să-l schimbăm cu ultimul nod, adică. (9). După ștergerea elementului rădăcină, trebuie din nou să-l îngrămădim pentru a-l converti în heap maxim.

După schimbarea elementului de matrice 76 cu 9 și transformând heap-ul în max-heap, elementele matricei sunt -

În pasul următor, din nou trebuie să ștergem elementul rădăcină (54) din grămada maximă. Pentru a șterge acest nod, trebuie să-l schimbăm cu ultimul nod, adică. (14). După ștergerea elementului rădăcină, trebuie din nou să-l îngrămădim pentru a-l converti în heap maxim.

După schimbarea elementului de matrice 54 cu 14 și transformând heap-ul în max-heap, elementele matricei sunt -

În pasul următor, din nou trebuie să ștergem elementul rădăcină (22) din grămada maximă. Pentru a șterge acest nod, trebuie să-l schimbăm cu ultimul nod, adică. (unsprezece). După ștergerea elementului rădăcină, trebuie din nou să-l îngrămădim pentru a-l converti în heap maxim.

După schimbarea elementului de matrice 22 cu unsprezece și transformând heap-ul în max-heap, elementele matricei sunt -

În pasul următor, din nou trebuie să ștergem elementul rădăcină (14) din grămada maximă. Pentru a șterge acest nod, trebuie să-l schimbăm cu ultimul nod, adică. (9). După ștergerea elementului rădăcină, trebuie din nou să-l îngrămădim pentru a-l converti în heap maxim.

După schimbarea elementului de matrice 14 cu 9 și transformând heap-ul în max-heap, elementele matricei sunt -

În pasul următor, din nou trebuie să ștergem elementul rădăcină (unsprezece) din grămada maximă. Pentru a șterge acest nod, trebuie să-l schimbăm cu ultimul nod, adică. (9). După ștergerea elementului rădăcină, trebuie din nou să-l îngrămădim pentru a-l converti în heap maxim.

După schimbarea elementului de matrice unsprezece cu 9, elementele matricei sunt -

Acum, heap mai are un singur element. După ștergere, heap-ul va fi gol.

După terminarea sortării, elementele matricei sunt -

25 din 100

Acum, matricea este complet sortată.

Complexitatea sortării în grămada

Acum, să vedem complexitatea de timp a sortării Heap în cel mai bun caz, mediu și cel mai rău caz. Vom vedea, de asemenea, complexitatea spațială a Heapsort.

1. Complexitatea timpului

Complexitatea celui mai bun caz -Apare atunci când nu este necesară sortarea, adică matricea este deja sortată. Cel mai bun caz, complexitatea de timp a sortării heap este O(n log). Complexitatea medie a cazului -Apare atunci când elementele matricei sunt într-o ordine amestecată care nu este corect ascendentă și nu este corect descendentă. Complexitatea medie a timpului de caz a sortării heap este O(n log n). Complexitatea celui mai rău caz -Apare atunci când elementele matricei trebuie să fie sortate în ordine inversă. Aceasta înseamnă să presupunem că trebuie să sortați elementele matricei în ordine crescătoare, dar elementele sale sunt în ordine descrescătoare. Cel mai rău caz complexitatea de timp a sortării heap este O(n log n).

Complexitatea de timp a sortării heap este O(n log) în toate cele trei cazuri (cazul cel mai bun, cazul mediu și cel mai rău caz). Înălțimea unui arbore binar complet având n elemente este calm.

2. Complexitatea spațială

• Complexitatea spațială a sortării Heap este O(1).

Implementarea Heapsort

Acum, să vedem programele de sortare Heap în diferite limbaje de programare.

Program: Scrieți un program pentru a implementa sortarea heap în limbaj C.

 #include /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int arr[], int n) { for (int i = 0; i <n; ++i) { printf('%d', arr[i]); printf(' '); } int main() a[]="{48," 10, 23, 43, 28, 26, 1}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are - 
'); printarr(a, n); heapsort(a, printf('
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-20.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C++.</p> <pre> #include using namespace std; /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int a[], int n) { for (int i = 0; i <n; ++i) { cout< <a[i]<<' '; } int main() a[]="{47," 9, 22, 42, 27, 25, 0}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are - 
'; printarr(a, n); heapsort(a, cout<<'
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-21.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C#.</p> <pre> using System; class HeapSort { /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ static void heapify(int[] a, int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int[] a, int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{46," 8, 21, 41, 26, 24, -1}; int n="a.Length;" console.write('before sorting array elements are - 
'); printarr(a, n); heapsort(a, console.write('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-22.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in Java.</p> <pre> class HeapSort { /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ static void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{45," 7, 20, 40, 25, 23, -2}; n="a.length;" system.out.print('before sorting array elements are - 
'); printarr(a, n); heapsort(a, system.out.print('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-23.webp" alt="Heap Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;>