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 1ulfaza.
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.
statyczne słowo kluczowe w Javie
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ą -
mój flixer
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
| Sprawa | Złożoność czasu |
|---|---|
| Najlepszy przypadek | O(n log) |
| Przeciętny przypadek | O(n log n) |
| Najgorszy przypadek | 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ść przestrzeni | O(1) |
| Stabilny | Nie |
- 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 '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;>