Î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 1Sffază.
Î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
| Caz | Complexitatea timpului |
|---|---|
| Cel mai bun caz | O(n log) |
| Caz mediu | O(n log n) |
| Cel mai rău caz | 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ă | O(1) |
| Grajd | N0 |
- 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 'i' is the index of root node in array a[], and 'n' 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 >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 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 'i' is the index of root node in array a[], and 'n' 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 >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 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 'i' is the index of root node in array a[], and 'n' 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 >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 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 'i' is the index of root node in array a[], and 'n' 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 >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 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's all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;>