I denne artikkelen vil vi diskutere Heapsort-algoritmen. Heap-sortering behandler elementene ved å lage min-heapen eller max-heapen ved å bruke elementene i den gitte matrisen. Min-heap eller max-heap representerer rekkefølgen av matrisen der rotelementet representerer minimums- eller maksimumselementet til matrisen.
Heapsortering utfører i utgangspunktet to hovedoperasjoner rekursivt -
- Bygg en haug H ved å bruke elementene i array.
- Slett rotelementet til haugen som er dannet i 1 gjentatte gangerstfase.
Før vi vet mer om haugsortering, la oss først se en kort beskrivelse av Heap.
Hva er en haug?
En haug er et komplett binært tre, og det binære treet er et tre der noden kan ha de ytterste to barn. Et komplett binært tre er et binært tre der alle nivåene unntatt det siste nivået, dvs. bladnoden, skal være fullstendig fylt, og alle nodene skal venstrejusteres.
Hva er haugsortering?
Heapsort er en populær og effektiv sorteringsalgoritme. Konseptet med haugsortering er å eliminere elementene en etter en fra haugdelen av listen, og deretter sette dem inn i den sorterte delen av listen.
Heapsort er sorteringsalgoritmen på stedet.
linux-vert
La oss nå se algoritmen for haugeslag.
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
La oss nå se hvordan Heapsort-algoritmen fungerer.
I haugsortering er det i utgangspunktet to faser involvert i sorteringen av elementer. Ved å bruke heap-sorteringsalgoritmen er de som følger -
- Det første trinnet inkluderer opprettelsen av en haug ved å justere elementene i matrisen.
- Etter opprettelsen av haugen, fjern nå rotelementet av haugen gjentatte ganger ved å flytte den til slutten av arrayen, og lagre deretter haugstrukturen med de gjenværende elementene.
La oss nå se hvordan haugsortering fungerer i detalj ved å bruke et eksempel. For å forstå det klarere, la oss ta en usortert matrise og prøve å sortere den ved hjelp av heap-sortering. Det vil gjøre forklaringen klarere og enklere.
Først må vi konstruere en haug fra den gitte matrisen og konvertere den til maks haug.
Etter å ha konvertert den gitte haugen til maksimal haug, er array-elementene -
Deretter må vi slette rotelementet (89) fra makshaugen. For å slette denne noden må vi bytte den med den siste noden, dvs. (elleve). Etter å ha slettet rotelementet, må vi igjen heapify det for å konvertere det til max heap.
Etter å ha byttet array-elementet 89 med elleve, og konverterer haugen til max-heap, elementene i array er -
I neste trinn, igjen, må vi slette rotelementet (81) fra makshaugen. For å slette denne noden må vi bytte den med den siste noden, dvs. (54). Etter å ha slettet rotelementet, må vi igjen heapify det for å konvertere det til max heap.
Etter å ha byttet array-elementet 81 med 54 og konverterer haugen til max-heap, elementene i array er -
I neste trinn må vi slette rotelementet (76) fra makshaugen igjen. For å slette denne noden må vi bytte den med den siste noden, dvs. (9). Etter å ha slettet rotelementet, må vi igjen heapify det for å konvertere det til max heap.
Etter å ha byttet array-elementet 76 med 9 og konverterer haugen til max-heap, elementene i array er -
I neste trinn må vi igjen slette rotelementet (54) fra makshaugen. For å slette denne noden må vi bytte den med den siste noden, dvs. (14). Etter å ha slettet rotelementet, må vi igjen heapify det for å konvertere det til max heap.
Etter å ha byttet array-elementet 54 med 14 og konverterer haugen til max-heap, elementene i array er -
I neste trinn må vi igjen slette rotelementet (22) fra makshaugen. For å slette denne noden må vi bytte den med den siste noden, dvs. (elleve). Etter å ha slettet rotelementet, må vi igjen heapify det for å konvertere det til max heap.
Etter å ha byttet array-elementet 22 med elleve og konverterer haugen til max-heap, elementene i array er -
I neste trinn må vi igjen slette rotelementet (14) fra makshaugen. For å slette denne noden må vi bytte den med den siste noden, dvs. (9). Etter å ha slettet rotelementet, må vi igjen heapify det for å konvertere det til max heap.
Etter å ha byttet array-elementet 14 med 9 og konverterer haugen til max-heap, elementene i array er -
I neste trinn må vi igjen slette rotelementet (elleve) fra makshaugen. For å slette denne noden må vi bytte den med den siste noden, dvs. (9). Etter å ha slettet rotelementet, må vi igjen heapify det for å konvertere det til max heap.
Etter å ha byttet array-elementet elleve med 9, elementene i array er -
Nå har heap bare ett element igjen. Etter å ha slettet den, vil haugen være tom.
Etter fullført sortering er array-elementene -
Nå er matrisen fullstendig sortert.
Heap sort kompleksitet
La oss nå se tidskompleksiteten til Heap-sortering i beste tilfelle, gjennomsnittlig tilfelle og verste tilfelle. Vi vil også se plasskompleksiteten til Heapsort.
cm til fot og tommer
1. Tidskompleksitet
| Sak | Tidskompleksitet |
|---|---|
| Beste sak | O(n logn) |
| Gjennomsnittlig sak | O(n log n) |
| Worst Case | O(n log n) |
Tidskompleksiteten til haugsortering er O(n logn) i alle tre tilfellene (beste tilfelle, gjennomsnittlig tilfelle og verste tilfelle). Høyden på et komplett binært tre med n elementer er rolig.
2. Romkompleksitet
| Plass kompleksitet | O(1) |
| Stabil | N0 |
- Romkompleksiteten til Heap-sortering er O(1).
Implementering av Heapsort
La oss nå se programmene til Heap sortere på forskjellige programmeringsspråk.
Program: Skriv et program for å implementere heap-sortering i C-språk.
#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;>