I den här artikeln kommer vi att diskutera Heapsort-algoritmen. Högsortering bearbetar elementen genom att skapa min-högen eller max-högen med hjälp av elementen i den givna arrayen. Min-hög eller max-hög representerar ordningen av array där rotelementet representerar minsta eller maximala elementet i arrayen.
Högsortering utför i princip rekursivt två huvudoperationer -
- Bygg en hög H, med hjälp av elementen i array.
- Ta bort rotelementet i högen som bildas i 1 upprepade gångerstfas.
Innan vi vet mer om högsorteringen, låt oss först se en kort beskrivning av Högen.
Vad är en hög?
En hög är ett komplett binärt träd, och det binära trädet är ett träd där noden kan ha de yttersta två barnen. Ett komplett binärt träd är ett binärt träd där alla nivåer utom den sista nivån, dvs lövnoden, ska vara helt fyllda och alla noder ska vara vänsterjusterade.
Vad är heap sort?
Heapsort är en populär och effektiv sorteringsalgoritm. Konceptet med högsortering är att eliminera elementen en efter en från högdelen av listan och sedan infoga dem i den sorterade delen av listan.
Heapsort är sorteringsalgoritmen på plats.
intern drift av hashmap
Låt oss nu se algoritmen för högsort.
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
Arbetar med Heap sort Algorithm
Låt oss nu se hur Heapsort-algoritmen fungerar.
I högsortering finns i princip två faser involverade i sorteringen av element. Genom att använda heap-sorteringsalgoritmen är de följande -
- Det första steget inkluderar skapandet av en heap genom att justera elementen i arrayen.
- Efter skapandet av högen, ta nu bort rotelementet från högen upprepade gånger genom att flytta det till slutet av matrisen och lagra sedan högstrukturen med de återstående elementen.
Låt oss nu se hur högsorteringen fungerar i detalj med hjälp av ett exempel. För att förstå det tydligare, låt oss ta en osorterad array och försöka sortera den med hjälp av högsortering. Det kommer att göra förklaringen tydligare och lättare.
Först måste vi konstruera en hög från den givna arrayen och omvandla den till maxhög.
Efter att ha konverterat den givna högen till maxhög, är arrayelementen -
Därefter måste vi ta bort rotelementet (89) från maxhögen. För att ta bort denna nod måste vi byta ut den med den sista noden, dvs. (elva). Efter att ha tagit bort rotelementet måste vi återigen heapify det för att konvertera det till max heap.
Efter att ha bytt arrayelementet 89 med elva, och omvandlar högen till max-hög, elementen i array är -
I nästa steg måste vi återigen ta bort rotelementet (81) från maxhögen. För att ta bort denna nod måste vi byta ut den med den sista noden, dvs. (54). Efter att ha tagit bort rotelementet måste vi återigen heapify det för att konvertera det till max heap.
Efter att ha bytt arrayelementet 81 med 54 och omvandlar högen till max-hög, elementen i array är -
I nästa steg måste vi ta bort rotelementet (76) från maxhögen igen. För att ta bort denna nod måste vi byta ut den med den sista noden, dvs. (9). Efter att ha tagit bort rotelementet måste vi återigen heapify det för att konvertera det till max heap.
Efter att ha bytt arrayelementet 76 med 9 och omvandlar högen till max-hög, elementen i array är -
I nästa steg måste vi återigen ta bort rotelementet (54) från maxhögen. För att ta bort denna nod måste vi byta ut den med den sista noden, dvs. (14). Efter att ha tagit bort rotelementet måste vi återigen heapify det för att konvertera det till max heap.
Efter att ha bytt arrayelementet 54 med 14 och omvandlar högen till max-hög, elementen i array är -
I nästa steg måste vi återigen ta bort rotelementet (22) från maxhögen. För att ta bort denna nod måste vi byta ut den med den sista noden, dvs. (elva). Efter att ha tagit bort rotelementet måste vi återigen heapify det för att konvertera det till max heap.
Efter att ha bytt arrayelementet 22 med elva och omvandlar högen till max-hög, elementen i array är -
I nästa steg måste vi återigen ta bort rotelementet (14) från maxhögen. För att ta bort denna nod måste vi byta ut den med den sista noden, dvs. (9). Efter att ha tagit bort rotelementet måste vi återigen heapify det för att konvertera det till max heap.
Efter att ha bytt arrayelementet 14 med 9 och omvandlar högen till max-hög, elementen i array är -
I nästa steg måste vi återigen ta bort rotelementet (elva) från maxhögen. För att ta bort denna nod måste vi byta ut den med den sista noden, dvs. (9). Efter att ha tagit bort rotelementet måste vi återigen heapify det för att konvertera det till max heap.
boto3
Efter att ha bytt arrayelementet elva med 9, elementen i array är -
Nu har heap bara ett element kvar. Efter att ha raderat den kommer högen att vara tom.
Efter slutförd sortering är arrayelementen -
Nu är arrayen helt sorterad.
Hög sorts komplexitet
Låt oss nu se tidskomplexiteten för Heap-sortering i bästa fall, genomsnittligt fall och värsta fall. Vi kommer också att se rymdkomplexiteten hos Heapsort.
1. Tidskomplexitet
| Fall | Tidskomplexitet |
|---|---|
| Bästa fall | O(n log) |
| Genomsnittligt fall | O(n log n) |
| Värsta fall | O(n log n) |
Tidskomplexiteten för högsort är O(n log) i alla tre fallen (bästa fall, genomsnittligt fall och värsta fall). Höjden på ett komplett binärt träd som har n element är lugna.
2. Rymdkomplexitet
| Rymdkomplexitet | O(1) |
| Stabil | N0 |
- Rymdkomplexiteten för Heap-sortering är O(1).
Implementering av Heapsort
Låt oss nu se hur Heap-programmen sorteras på olika programmeringsspråk.
Program: Skriv ett program för att implementera heapsortering 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;>