I denne artikel vil vi diskutere Heapsort-algoritmen. Heap-sortering behandler elementerne ved at skabe min-heapen eller max-heapen ved hjælp af elementerne i det givne array. Min-heap eller max-heap repræsenterer rækkefølgen af array, hvor rodelementet repræsenterer minimum- eller maksimumelementet i arrayet.
Heap sortering udfører grundlæggende rekursivt to hovedoperationer -
- Byg en bunke H ved hjælp af elementerne i array.
- Slet gentagne gange rodelementet af heapen dannet i 1stfase.
Inden vi ved mere om bunken, lad os først se en kort beskrivelse af Dynge.
Hvad er en bunke?
En bunke er et komplet binært træ, og det binære træ er et træ, hvor noden kan have de yderste to børn. Et komplet binært træ er et binært træ, hvor alle niveauerne undtagen det sidste niveau, dvs. bladknudepunktet, skal være fuldstændigt udfyldt, og alle noderne skal venstrejusteres.
Hvad er heap sort?
Heapsort er en populær og effektiv sorteringsalgoritme. Konceptet med heap-sortering er at fjerne elementerne en efter en fra heap-delen af listen og derefter indsætte dem i den sorterede del af listen.
Heapsort er sorteringsalgoritmen på stedet.
dato konvertere til streng
Lad os nu se algoritmen for heap-sort.
Algoritme
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
Working of Heap sort Algorithm
Lad os nu se, hvordan Heapsort-algoritmen fungerer.
I heap-sortering er der grundlæggende to faser involveret i sorteringen af elementer. Ved at bruge heap-sorteringsalgoritmen er de som følger -
- Det første trin inkluderer oprettelsen af en heap ved at justere elementerne i arrayet.
- Efter oprettelsen af heap skal du nu fjerne rodelementet af heapen gentagne gange ved at flytte det til enden af arrayet, og derefter gemme heapstrukturen med de resterende elementer.
Lad os nu se, hvordan heap-sortering fungerer i detaljer ved at bruge et eksempel. For at forstå det mere klart, lad os tage et usorteret array og prøve at sortere det ved hjælp af heap-sortering. Det vil gøre forklaringen klarere og lettere.
Først skal vi konstruere en heap fra det givne array og konvertere den til max heap.
Efter konvertering af den givne heap til max heap, er array-elementerne -
Dernæst skal vi slette rodelementet (89) fra den maksimale bunke. For at slette denne node, skal vi bytte den med den sidste node, dvs. (elleve). Efter at have slettet rodelementet, skal vi igen heapify det for at konvertere det til max heap.
Efter at have skiftet array-elementet 89 med elleve, og konverterer heapen til max-heap, er elementerne i array -
I det næste trin skal vi igen slette rodelementet (81) fra den maksimale bunke. For at slette denne node, skal vi bytte den med den sidste node, dvs. (54). Efter at have slettet rodelementet, skal vi igen heapify det for at konvertere det til max heap.
Efter at have skiftet array-elementet 81 med 54 og konverterer heapen til max-heap, er elementerne i array -
I næste trin skal vi slette rodelementet (76) fra max-bunken igen. For at slette denne node, skal vi bytte den med den sidste node, dvs. (9). Efter at have slettet rodelementet, skal vi igen heapify det for at konvertere det til max heap.
Efter at have skiftet array-elementet 76 med 9 og konverterer heapen til max-heap, er elementerne i array -
I næste trin skal vi igen slette rodelementet (54) fra den maksimale bunke. For at slette denne node, skal vi bytte den med den sidste node, dvs. (14). Efter at have slettet rodelementet, skal vi igen heapify det for at konvertere det til max heap.
Efter at have skiftet array-elementet 54 med 14 og konverterer heapen til max-heap, er elementerne i array -
I næste trin skal vi igen slette rodelementet (22) fra den maksimale bunke. For at slette denne node, skal vi bytte den med den sidste node, dvs. (elleve). Efter at have slettet rodelementet, skal vi igen heapify det for at konvertere det til max heap.
Efter at have skiftet array-elementet 22 med elleve og konverterer heapen til max-heap, er elementerne i array -
I næste trin skal vi igen slette rodelementet (14) fra den maksimale bunke. For at slette denne node, skal vi bytte den med den sidste node, dvs. (9). Efter at have slettet rodelementet, skal vi igen heapify det for at konvertere det til max heap.
Efter at have skiftet array-elementet 14 med 9 og konverterer heapen til max-heap, er elementerne i array -
I næste trin skal vi igen slette rodelementet (elleve) fra den maksimale bunke. For at slette denne node, skal vi bytte den med den sidste node, dvs. (9). Efter at have slettet rodelementet, skal vi igen heapify det for at konvertere det til max heap.
Efter at have skiftet array-elementet elleve med 9, elementerne i array er -
Nu har heap kun ét element tilbage. Efter sletning er heap tom.
Efter afslutning af sortering er array-elementerne -
Nu er arrayet helt sorteret.
Dynge sorterings kompleksitet
Lad os nu se tidskompleksiteten af Heap-sortering i bedste tilfælde, gennemsnitligt tilfælde og værste tilfælde. Vi vil også se pladskompleksiteten i Heapsort.
hvor mange 0 i en milliard
1. Tidskompleksitet
| Sag | Tidskompleksitet |
|---|---|
| Bedste sag | O(n log) |
| Gennemsnitlig tilfælde | O(n log n) |
| Worst Case | O(n log n) |
Tidskompleksiteten af bunkesortering er O(n log) i alle tre tilfælde (bedste tilfælde, gennemsnitligt tilfælde og værste tilfælde). Højden af et komplet binært træ med n elementer er berolige.
2. Rumkompleksitet
| Rumkompleksitet | O(1) |
| Stabil | N0 |
- Rumkompleksiteten af Heap-sortering er O(1).
Implementering af Heapsort
Lad os nu se programmerne i Heap sortere på forskellige programmeringssprog.
Program: Skriv et program til at implementere heap-sortering i C-sprog.
#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;>