Šiame straipsnyje aptarsime „Heapsort“ algoritmą. Krūvos rūšiavimas apdoroja elementus sukurdamas min-heap arba max-heap, naudodamas nurodyto masyvo elementus. Min-heap arba max-heap reiškia masyvo tvarką, kurioje šakninis elementas reiškia mažiausią arba didžiausią masyvo elementą.
Krūvos rūšiavimas iš esmės rekursyviai atlieka dvi pagrindines operacijas -
- Sukurkite krūvą H, naudodami masyvo elementus.
- Pakartotinai ištrinkite 1 suformuotos krūvos šakninį elementąŠvfazė.
Prieš sužinodami daugiau apie krūvos rūšiavimą, pirmiausia pažiūrėkime trumpą aprašymą Krūva.
Kas yra krūva?
Krūva yra pilnas dvejetainis medis, o dvejetainis medis yra medis, kuriame mazgas gali turėti daugiausiai du vaikus. Pilnas dvejetainis medis yra dvejetainis medis, kuriame visi lygiai, išskyrus paskutinį lygį, t. y. lapo mazgą, turi būti visiškai užpildyti, o visi mazgai turi būti išlyginti kairėje pusėje.
Kas yra krūvos rūšiavimas?
Heapsort yra populiarus ir efektyvus rūšiavimo algoritmas. Krūvos rūšiavimo koncepcija yra pašalinti elementus po vieną iš sąrašo krūvos dalies ir įterpti juos į surūšiuotą sąrašo dalį.
Heapssort yra rūšiavimo vietoje algoritmas.
java pagrindai
Dabar pažiūrėkime krūvos rūšiavimo algoritmą.
Algoritmas
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
Krūvos rūšiavimo algoritmo veikimas
Dabar pažiūrėkime, kaip veikia „Heapsort“ algoritmas.
Iš esmės rūšiuojant krūvą elementai rūšiuojami dviem etapais. Naudojant krūvos rūšiavimo algoritmą, jie yra tokie:
- Pirmasis žingsnis apima krūvos sukūrimą koreguojant masyvo elementus.
- Sukūrę krūvą, dabar pakartotinai pašalinkite šakninį krūvos elementą, perkeldami jį į masyvo galą, tada išsaugokite krūvos struktūrą su likusiais elementais.
Dabar pažiūrėkime, kaip veikia krūvos rūšiavimas, naudodami pavyzdį. Norėdami tai suprasti aiškiau, paimkime nerūšiuotą masyvą ir pabandykite jį surūšiuoti naudodami krūvos rūšiavimą. Tai padarys paaiškinimą aiškesnį ir lengvesnį.
Pirmiausia turime sukurti krūvą iš nurodyto masyvo ir konvertuoti jį į didžiausią krūvą.
Konvertavus nurodytą krūvą į didžiausią krūvą, masyvo elementai yra -
Tada turime ištrinti šakninį elementą (89) nuo maksimalaus krūvos. Norėdami ištrinti šį mazgą, turime jį sukeisti su paskutiniu mazgu, t.y. (vienuolika). Ištrynę šakninį elementą, vėl turime jį paversti į didžiausią krūvą.
Pakeitus masyvo elementą 89 su vienuolika, ir konvertuojant krūvą į didžiausią krūvą, masyvo elementai yra -
Kitame žingsnyje vėl turime ištrinti šakninį elementą (81) nuo maksimalaus krūvos. Norėdami ištrinti šį mazgą, turime jį sukeisti su paskutiniu mazgu, t.y. (54). Ištrynę šakninį elementą, vėl turime jį paversti į didžiausią krūvą.
Pakeitus masyvo elementą 81 su 54 ir konvertuojant krūvą į didžiausią krūvą, masyvo elementai yra -
Kitame žingsnyje turime ištrinti šakninį elementą (76) vėl iš maksimalaus krūvos. Norėdami ištrinti šį mazgą, turime jį sukeisti su paskutiniu mazgu, t.y. (9). Ištrynę šakninį elementą, vėl turime jį paversti į didžiausią krūvą.
Pakeitus masyvo elementą 76 su 9 ir konvertuojant krūvą į didžiausią krūvą, masyvo elementai yra -
java konvertuoti eilutę į int
Kitame žingsnyje vėl turime ištrinti šakninį elementą (54) nuo maksimalaus krūvos. Norėdami ištrinti šį mazgą, turime jį sukeisti su paskutiniu mazgu, t.y. (14). Ištrynę šakninį elementą, vėl turime jį paversti į didžiausią krūvą.
Pakeitus masyvo elementą 54 su 14 ir konvertuojant krūvą į didžiausią krūvą, masyvo elementai yra -
Kitame žingsnyje vėl turime ištrinti šakninį elementą (22) nuo maksimalaus krūvos. Norėdami ištrinti šį mazgą, turime jį sukeisti su paskutiniu mazgu, t.y. (vienuolika). Ištrynę šakninį elementą, vėl turime jį paversti į didžiausią krūvą.
Pakeitus masyvo elementą 22 su vienuolika ir konvertuojant krūvą į didžiausią krūvą, masyvo elementai yra -
Kitame žingsnyje vėl turime ištrinti šakninį elementą (14) nuo maksimalaus krūvos. Norėdami ištrinti šį mazgą, turime jį sukeisti su paskutiniu mazgu, t.y. (9). Ištrynę šakninį elementą, vėl turime jį paversti į didžiausią krūvą.
Pakeitus masyvo elementą 14 su 9 ir konvertuojant krūvą į didžiausią krūvą, masyvo elementai yra -
Kitame žingsnyje vėl turime ištrinti šakninį elementą (vienuolika) nuo maksimalaus krūvos. Norėdami ištrinti šį mazgą, turime jį sukeisti su paskutiniu mazgu, t.y. (9). Ištrynę šakninį elementą, vėl turime jį paversti į didžiausią krūvą.
Pakeitus masyvo elementą vienuolika su 9, masyvo elementai yra -
Dabar krūvoje liko tik vienas elementas. Ją ištrynus, krūva bus tuščia.
Baigę rūšiavimą, masyvo elementai yra -
Dabar masyvas yra visiškai surūšiuotas.
Krūvos rūšiavimo sudėtingumas
Dabar pažiūrėkime į krūvos rūšiavimo laiko sudėtingumą geriausiu, vidutiniu ir blogiausiu atveju. Taip pat pamatysime „Heapsort“ erdvės sudėtingumą.
1. Laiko sudėtingumas
| Byla | Laiko sudėtingumas |
|---|---|
| Geriausias atvejis | O (n log) |
| Vidutinis atvejis | O(n log n) |
| Blogiausiu atveju | O(n log n) |
Krūvos rūšiavimo laiko sudėtingumas yra O (n log) visais trimis atvejais (geriausiu, vidutiniu ir blogiausiu atveju). Viso dvejetainio medžio, turinčio n elementų, aukštis yra Ramus.
2. Erdvės sudėtingumas
| Erdvės sudėtingumas | O(1) |
| Stabilus | N0 |
- Krūvos rūšiavimo erdvės sudėtingumas yra O(1).
„Heapsort“ diegimas
Dabar pažiūrėkime, kaip Heap programos rūšiuojamos skirtingomis programavimo kalbomis.
Programa: Parašykite programą, kuri įgyvendintų krūvos rūšiavimą C kalba.
#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;>