W tym artykule omówimy algorytm Heapsort. Sortowanie sterty przetwarza elementy, tworząc stertę minimalną lub stertę maksymalną przy użyciu elementów danej tablicy. Min-sterta lub max-heap reprezentuje kolejność tablicy, w której element główny reprezentuje minimalny lub maksymalny element tablicy.

Sortowanie sterty zasadniczo rekurencyjnie wykonuje dwie główne operacje -

• Zbuduj stertę H, korzystając z elementów tablicy.
• Wielokrotnie usuń element główny sterty utworzonej w 1 ^ul faza.

Zanim dowiemy się więcej o sortowaniu sterty, przyjrzyjmy się najpierw krótkiemu opisowi Sterta.

Co to jest kupa?

Kopiec jest kompletnym drzewem binarnym, a drzewo binarne jest drzewem, w którym węzeł może mieć maksymalnie dwoje dzieci. Kompletne drzewo binarne to drzewo binarne, w którym wszystkie poziomy z wyjątkiem ostatniego, czyli węzła liścia, powinny być całkowicie wypełnione, a wszystkie węzły powinny być wyrównane do lewej strony.

Co to jest sortowanie sterty?

Heapsort to popularny i wydajny algorytm sortowania. Koncepcja sortowania na stercie polega na eliminowaniu elementów jeden po drugim ze sterty części listy, a następnie wstawianiu ich do posortowanej części listy.

Heapsort to algorytm sortowania w miejscu.

Przyjrzyjmy się teraz algorytmowi sortowania sterty.

Algorytm

 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  

Działanie algorytmu sortowania sterty

Przyjrzyjmy się teraz działaniu algorytmu Heapsort.

W zasadzie sortowanie na stercie obejmuje dwie fazy sortowania elementów. Używając algorytmu sortowania sterty, są one następujące:

• Pierwszy krok obejmuje utworzenie sterty poprzez dopasowanie elementów tablicy.
• Po utworzeniu sterty usuń teraz wielokrotnie element główny sterty, przesuwając go na koniec tablicy, a następnie zapisz strukturę sterty z pozostałymi elementami.

Przyjrzyjmy się teraz szczegółowo działaniu sortowania na stercie na przykładzie. Aby to lepiej zrozumieć, weźmy nieposortowaną tablicę i spróbujmy ją posortować za pomocą sortowania przez stertę. Dzięki temu wyjaśnienia będą jaśniejsze i łatwiejsze.

Najpierw musimy skonstruować stertę z podanej tablicy i przekonwertować ją na maksymalną stertę.

Po przekonwertowaniu danej sterty na maksymalną stertę elementy tablicy to -

Następnie musimy usunąć element główny (89) z maksymalnej sterty. Aby usunąć ten węzeł, musimy zamienić go z ostatnim węzłem, tj. (jedenaście). Po usunięciu elementu głównego musimy go ponownie spakować, aby przekonwertować go na maksymalną stertę.

Po zamianie elementu tablicy 89 z jedenaście, i konwertując stertę na maksymalną stertę, elementami tablicy są -

W następnym kroku ponownie musimy usunąć element główny (81) z maksymalnej sterty. Aby usunąć ten węzeł, musimy zamienić go z ostatnim węzłem, tj. (54). Po usunięciu elementu głównego musimy go ponownie spakować, aby przekonwertować go na maksymalną stertę.

Po zamianie elementu tablicy 81 z 54 i konwertując stertę na maksymalną stertę, elementami tablicy są -

W kolejnym kroku musimy usunąć element główny (76) ponownie z maksymalnej sterty. Aby usunąć ten węzeł, musimy zamienić go z ostatnim węzłem, tj. (9). Po usunięciu elementu głównego musimy go ponownie spakować, aby przekonwertować go na maksymalną stertę.

Po zamianie elementu tablicy 76 z 9 i konwertując stertę na maksymalną stertę, elementami tablicy są -

W kolejnym kroku ponownie musimy usunąć element główny (54) z maksymalnej sterty. Aby usunąć ten węzeł, musimy zamienić go z ostatnim węzłem, tj. (14). Po usunięciu elementu głównego musimy go ponownie spakować, aby przekonwertować go na maksymalną stertę.

Po zamianie elementu tablicy 54 z 14 i konwertując stertę na maksymalną stertę, elementami tablicy są -

W kolejnym kroku ponownie musimy usunąć element główny (22) z maksymalnej sterty. Aby usunąć ten węzeł, musimy zamienić go z ostatnim węzłem, tj. (jedenaście). Po usunięciu elementu głównego musimy go ponownie spakować, aby przekonwertować go na maksymalną stertę.

Po zamianie elementu tablicy 22 z jedenaście i konwertując stertę na maksymalną stertę, elementami tablicy są -

W kolejnym kroku ponownie musimy usunąć element główny (14) z maksymalnej sterty. Aby usunąć ten węzeł, musimy zamienić go z ostatnim węzłem, tj. (9). Po usunięciu elementu głównego musimy go ponownie spakować, aby przekonwertować go na maksymalną stertę.

Po zamianie elementu tablicy 14 z 9 i konwertując stertę na maksymalną stertę, elementami tablicy są -

W kolejnym kroku ponownie musimy usunąć element główny (jedenaście) z maksymalnej sterty. Aby usunąć ten węzeł, musimy zamienić go z ostatnim węzłem, tj. (9). Po usunięciu elementu głównego musimy go ponownie spakować, aby przekonwertować go na maksymalną stertę.

Po zamianie elementu tablicy jedenaście z 9, elementy tablicy to -

Teraz na stercie pozostał tylko jeden element. Po jego usunięciu sterta będzie pusta.

Po zakończeniu sortowania elementy tablicy są -

Teraz tablica jest całkowicie posortowana.

Złożoność sortowania sterty

Przyjrzyjmy się teraz złożoności czasowej sortowania sterty w najlepszym, średnim i najgorszym przypadku. Zobaczymy także złożoność przestrzenną Heapsort.

1. Złożoność czasowa

Najlepsza złożoność przypadku — Występuje, gdy nie jest wymagane sortowanie, czyli tablica jest już posortowana. W najlepszym przypadku złożoność czasowa sortowania sterty wynosi O(n log). Średnia złożoność przypadku — Dzieje się tak, gdy elementy tablicy są w pomieszanej kolejności, która nie jest prawidłowo rosnąca i nieprawidłowo malejąca. Średnia złożoność czasowa sortowania sterty wynosi O(n log n). Najgorsza złożoność przypadku — Występuje, gdy elementy tablicy muszą zostać posortowane w odwrotnej kolejności. Oznacza to, że załóżmy, że musisz posortować elementy tablicy w kolejności rosnącej, ale jej elementy są w kolejności malejącej. Najgorszy przypadek złożoności czasowej sortowania sterty to O(n log n).

Złożoność czasowa sortowania na stercie wynosi O(n log) we wszystkich trzech przypadkach (najlepszy przypadek, średni przypadek i najgorszy przypadek). Wysokość pełnego drzewa binarnego mającego n elementów wynosi spokój.

2. Złożoność przestrzeni

• Złożoność przestrzenna sortowania sterty wynosi O(1).

Implementacja Heapsortu

Teraz przyjrzyjmy się programom Heap sortującym w różnych językach programowania.

Program: Napisz program realizujący sortowanie sterty w języku C.

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