In dit artikel bespreken we het Heapsort-algoritme. Heap sort verwerkt de elementen door de min-heap of max-heap te maken met behulp van de elementen van de gegeven array. Min-heap of max-heap vertegenwoordigt de volgorde van de array waarin het rootelement het minimale of maximale element van de array vertegenwoordigt.

Heap sort voert in principe recursief twee hoofdbewerkingen uit:

• Bouw een heap H, met behulp van de elementen van array.
• Verwijder herhaaldelijk het hoofdelement van de heap gevormd in 1^stfase.

Voordat we meer weten over de heap-soort, laten we eerst een korte beschrijving bekijken van Hoop.

Wat is een hoop?

Een heap is een volledige binaire boom, en de binaire boom is een boom waarin het knooppunt maximaal twee kinderen kan hebben. Een volledige binaire boom is een binaire boom waarin alle niveaus behalve het laatste niveau, d.w.z. het bladknooppunt, volledig gevuld moeten zijn, en alle knooppunten links uitgelijnd moeten zijn.

Wat is heapsortering?

Heapsort is een populair en efficiënt sorteeralgoritme. Het concept van heap sort is om de elementen één voor één uit het heap-gedeelte van de lijst te verwijderen en ze vervolgens in het gesorteerde deel van de lijst in te voegen.

Heapsort is het in-place sorteeralgoritme.

powershell kleiner dan of gelijk aan

Laten we nu eens kijken naar het algoritme van 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 

Werking van Heap sort-algoritme

Laten we nu eens kijken naar de werking van het Heapsort-algoritme.

Bij heap sort zijn er in principe twee fasen betrokken bij het sorteren van elementen. Door het heap sort-algoritme te gebruiken, zijn ze als volgt:

• De eerste stap omvat het maken van een heap door de elementen van de array aan te passen.
• Na het maken van de heap verwijdert u nu herhaaldelijk het hoofdelement van de heap door het naar het einde van de array te verschuiven en slaat u vervolgens de heap-structuur op met de overige elementen.

Laten we nu de werking van heap sort in detail bekijken aan de hand van een voorbeeld. Om het duidelijker te begrijpen, nemen we een ongesorteerde array en proberen deze te sorteren met behulp van heap sort. Het zal de uitleg duidelijker en gemakkelijker maken.

Eerst moeten we een heap construeren uit de gegeven array en deze omzetten in max heap.

Na het converteren van de gegeven heap naar max heap, zijn de array-elementen -

Vervolgens moeten we het rootelement verwijderen (89) van de maximale hoop. Om dit knooppunt te verwijderen, moeten we het omwisselen met het laatste knooppunt, d.w.z. (elf). Nadat we het rootelement hebben verwijderd, moeten we het opnieuw heapificeren om het naar max heap te converteren.

Na het verwisselen van het array-element 89 met elf, en door de heap om te zetten in max-heap, zijn de elementen van array -

In de volgende stap moeten we opnieuw het rootelement verwijderen (81) van de maximale hoop. Om dit knooppunt te verwijderen, moeten we het omwisselen met het laatste knooppunt, d.w.z. (54). Nadat we het rootelement hebben verwijderd, moeten we het opnieuw heapificeren om het naar max heap te converteren.

Na het verwisselen van het array-element 81 met 54 en door de heap om te zetten in max-heap, zijn de elementen van array -

In de volgende stap moeten we het rootelement verwijderen (76) opnieuw van de maximale heap. Om dit knooppunt te verwijderen, moeten we het omwisselen met het laatste knooppunt, d.w.z. (9). Nadat we het rootelement hebben verwijderd, moeten we het opnieuw heapificeren om het naar max heap te converteren.

Na het verwisselen van het array-element 76 met 9 en door de heap om te zetten in max-heap, zijn de elementen van array -

In de volgende stap moeten we opnieuw het rootelement verwijderen (54) van de maximale hoop. Om dit knooppunt te verwijderen, moeten we het omwisselen met het laatste knooppunt, d.w.z. (14). Nadat we het rootelement hebben verwijderd, moeten we het opnieuw heapificeren om het naar max heap te converteren.

Na het verwisselen van het array-element 54 met 14 en door de heap om te zetten in max-heap, zijn de elementen van array -

In de volgende stap moeten we opnieuw het rootelement verwijderen (22) van de maximale hoop. Om dit knooppunt te verwijderen, moeten we het omwisselen met het laatste knooppunt, d.w.z. (elf). Nadat we het rootelement hebben verwijderd, moeten we het opnieuw heapificeren om het naar max heap te converteren.

Na het verwisselen van het array-element 22 met elf en door de heap om te zetten in max-heap, zijn de elementen van array -

wiskundige methoden in Java

In de volgende stap moeten we opnieuw het rootelement verwijderen (14) van de maximale hoop. Om dit knooppunt te verwijderen, moeten we het omwisselen met het laatste knooppunt, d.w.z. (9). Nadat we het rootelement hebben verwijderd, moeten we het opnieuw heapificeren om het naar max heap te converteren.

Na het verwisselen van het array-element 14 met 9 en door de heap om te zetten in max-heap, zijn de elementen van array -

In de volgende stap moeten we opnieuw het rootelement verwijderen (elf) van de maximale hoop. Om dit knooppunt te verwijderen, moeten we het omwisselen met het laatste knooppunt, d.w.z. (9). Nadat we het rootelement hebben verwijderd, moeten we het opnieuw heapificeren om het naar max heap te converteren.

Na het verwisselen van het array-element elf met 9, de elementen van array zijn -

Nu heeft heap nog maar één element over. Na het verwijderen is de heap leeg.

Na voltooiing van het sorteren zijn de array-elementen -

Nu is de array volledig gesorteerd.

Complexiteit van heapsortering

Laten we nu eens kijken naar de tijdscomplexiteit van Heap-sortering in het beste geval, het gemiddelde geval en het slechtste geval. We zullen ook de ruimtecomplexiteit van Heapsort zien.

1. Tijdcomplexiteit

Beste case-complexiteit -Het treedt op als er geen sortering nodig is, d.w.z. de array is al gesorteerd. De beste tijdscomplexiteit van heap-sortering is O(n logboek). Gemiddelde casuscomplexiteit -Het treedt op wanneer de array-elementen zich in een door elkaar geplaatste volgorde bevinden die niet goed oplopend en niet goed aflopend is. De gemiddelde case-time-complexiteit van heap-sortering is O(n logboek n). In het ergste geval complexiteit -Het treedt op wanneer de array-elementen in omgekeerde volgorde moeten worden gesorteerd. Dat betekent dat u de array-elementen in oplopende volgorde moet sorteren, maar de elementen ervan in aflopende volgorde. De worst-case tijdscomplexiteit van heap sort is O(n logboek n).

De tijdscomplexiteit van heap sort is O(n logboek) in alle drie de gevallen (beste geval, gemiddelde geval en slechtste geval). De hoogte van een volledige binaire boom met n elementen is kalm.

2. Ruimtecomplexiteit

• De ruimtecomplexiteit van Heap-sortering is O(1).

Implementatie van Heapsort

Laten we nu de programma's van Heap in verschillende programmeertalen bekijken.

Programma: Schrijf een programma om heap sort in C-taal te implementeren.

 #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;>