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ånger^stfas.

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

Best Case Complexity -Det inträffar när det inte krävs någon sortering, dvs arrayen är redan sorterad. Den bästa möjliga tidskomplexiteten för högsort är O(n log). Genomsnittlig ärendekomplexitet -Det inträffar när arrayelementen är i blandad ordning som inte är korrekt stigande och inte korrekt fallande. Den genomsnittliga falltidskomplexiteten för högsort är O(n log n). Worst Case Complexity -Det inträffar när arrayelementen måste sorteras i omvänd ordning. Det betyder att du måste sortera arrayelementen i stigande ordning, men dess element är i fallande ordning. Det värsta tänkbara tidskomplexiteten av högsort är 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

• 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 &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; 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 &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 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 &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; 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 &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 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 &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; 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 &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 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 &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; 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 &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 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&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;>