Šajā rakstā mēs apspriedīsim Heapsort algoritmu. Kaudzes kārtošana apstrādā elementus, izveidojot min-heap vai max-heap, izmantojot dotā masīva elementus. Min-heap vai max-heap apzīmē masīva secību, kurā saknes elements apzīmē masīva minimālo vai maksimālo elementu.
Kaudzes kārtošana būtībā rekursīvi veic divas galvenās darbības -
- Izveidojiet kaudzi H, izmantojot masīva elementus.
- Atkārtoti dzēsiet 1. veidā izveidotās kaudzes saknes elementustfāze.
Pirms uzzināt vairāk par kaudzes kārtošanu, vispirms apskatīsim īsu aprakstu Kaudze.
Kas ir kaudze?
Kaudze ir pilnīgs binārais koks, un binārais koks ir koks, kurā mezglam var būt maksimāli divi bērni. Pilnīgs binārais koks ir binārs koks, kurā visi līmeņi, izņemot pēdējo līmeni, t.i., lapas mezglu, ir pilnībā jāaizpilda, un visi mezgli ir jāpamato ar kreiso pusi.
Kas ir kaudzes šķirošana?
Heapsort ir populārs un efektīvs šķirošanas algoritms. Kaudzes kārtošanas jēdziens ir vienu pēc otra izņemt elementus no saraksta kaudzes daļas un pēc tam ievietot tos sakārtotajā saraksta daļā.
Heapsort ir kārtošanas algoritms vietā.
vba
Tagad apskatīsim kaudzes kārtošanas algoritmu.
Algoritms
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
Kaudzes kārtošanas algoritma darbība
Tagad apskatīsim Heapsort algoritma darbību.
Kaudzes kārtošanā būtībā elementu šķirošanā ir iesaistītas divas fāzes. Izmantojot kaudzes kārtošanas algoritmu, tie ir šādi:
- Pirmais solis ietver kaudzes izveidi, pielāgojot masīva elementus.
- Pēc kaudzes izveides tagad atkārtoti noņemiet kaudzes saknes elementu, pārvietojot to uz masīva beigām, un pēc tam saglabājiet kaudzes struktūru ar atlikušajiem elementiem.
Tagad aplūkosim kaudzes kārtošanas darbību, izmantojot piemēru. Lai to saprastu skaidrāk, ņemsim nešķirotu masīvu un mēģināsim to kārtot, izmantojot kaudzes kārtošanu. Tas padarīs skaidrojumu skaidrāku un vienkāršāku.
Pirmkārt, mums ir jākonstruē kaudze no dotā masīva un jāpārveido par maksimālo kaudzi.
Pēc dotās kaudzes konvertēšanas par maksimālo kaudzi, masīva elementi ir -
Tālāk mums ir jāizdzēš saknes elements (89) no maksimālās kaudzes. Lai dzēstu šo mezglu, tas ir jāmaina ar pēdējo mezglu, t.i. (vienpadsmit). Pēc saknes elementa dzēšanas mums tas atkal ir jāveido kaudzītē, lai to pārvērstu par maksimālo kaudzi.
Pēc masīva elementa nomaiņas 89 ar vienpadsmit, un pārvēršot kaudzi par maksimālo kaudzi, masīva elementi ir -
Nākamajā solī mums atkal ir jāizdzēš saknes elements (81) no maksimālās kaudzes. Lai dzēstu šo mezglu, tas ir jāmaina ar pēdējo mezglu, t.i. (54). Pēc saknes elementa dzēšanas mums tas atkal ir jāveido kaudzītē, lai to pārvērstu par maksimālo kaudzi.
Pēc masīva elementa nomaiņas 81 ar 54 un pārvēršot kaudzi par maksimālo kaudzi, masīva elementi ir -
Nākamajā darbībā mums ir jāizdzēš saknes elements (76) atkal no max kaudzes. Lai dzēstu šo mezglu, tas ir jāmaina ar pēdējo mezglu, t.i. (9). Pēc saknes elementa dzēšanas mums tas atkal ir jāveido kaudzītē, lai to pārvērstu par maksimālo kaudzi.
Pēc masīva elementa nomaiņas 76 ar 9 un pārvēršot kaudzi par maksimālo kaudzi, masīva elementi ir -
fmovies Indija
Nākamajā solī mums atkal ir jāizdzēš saknes elements (54) no maksimālās kaudzes. Lai dzēstu šo mezglu, tas ir jāmaina ar pēdējo mezglu, t.i. (14). Pēc saknes elementa dzēšanas mums tas atkal ir jāveido kaudzītē, lai to pārvērstu par maksimālo kaudzi.
Pēc masīva elementa nomaiņas 54 ar 14 un pārvēršot kaudzi par maksimālo kaudzi, masīva elementi ir -
Nākamajā solī mums atkal ir jāizdzēš saknes elements (22) no maksimālās kaudzes. Lai dzēstu šo mezglu, tas ir jāmaina ar pēdējo mezglu, t.i. (vienpadsmit). Pēc saknes elementa dzēšanas mums tas atkal ir jāveido kaudzītē, lai to pārvērstu par maksimālo kaudzi.
Pēc masīva elementa nomaiņas 22 ar vienpadsmit un pārvēršot kaudzi par maksimālo kaudzi, masīva elementi ir -
Nākamajā solī mums atkal ir jāizdzēš saknes elements (14) no maksimālās kaudzes. Lai dzēstu šo mezglu, tas ir jāmaina ar pēdējo mezglu, t.i. (9). Pēc saknes elementa dzēšanas mums tas atkal ir jāveido kaudzītē, lai to pārvērstu par maksimālo kaudzi.
Pēc masīva elementa nomaiņas 14 ar 9 un pārvēršot kaudzi par maksimālo kaudzi, masīva elementi ir -
Nākamajā solī mums atkal ir jāizdzēš saknes elements (vienpadsmit) no maksimālās kaudzes. Lai dzēstu šo mezglu, tas ir jāmaina ar pēdējo mezglu, t.i. (9). Pēc saknes elementa dzēšanas mums tas atkal ir jāveido kaudzītē, lai to pārvērstu par maksimālo kaudzi.
Pēc masīva elementa nomaiņas vienpadsmit ar 9, masīva elementi ir -
Tagad kaudzītei ir palicis tikai viens elements. Pēc tā dzēšanas kaudze būs tukša.
Pēc kārtošanas pabeigšanas masīva elementi ir -
Tagad masīvs ir pilnībā sakārtots.
Kaudzes kārtošanas sarežģītība
Tagad apskatīsim Heap kārtošanas laika sarežģītību labākajā, vidējā un sliktākajā gadījumā. Mēs redzēsim arī Heapsort kosmosa sarežģītību.
1. Laika sarežģītība
| Lieta | Laika sarežģītība |
|---|---|
| Labākais gadījums | O(n log) |
| Vidējais gadījums | O(n log n) |
| Sliktākajā gadījumā | O(n log n) |
Kaudzes kārtošanas laika sarežģītība ir O(n log) visos trīs gadījumos (labākajā gadījumā, vidējais gadījums un sliktākais gadījums). Pilna bināra koka augstums ar n elementiem ir mierīgs.
2. Telpas sarežģītība
| Kosmosa sarežģītība | O(1) |
| Stabils | N0 |
- Kaudzes kārtošanas telpas sarežģītība ir O(1).
Heapsort ieviešana
Tagad apskatīsim Heap programmu šķirošanu dažādās programmēšanas valodās.
Programma: Uzrakstiet programmu kaudzes kārtošanai C valodā.
#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;>