Sortowanie sterty to technika sortowania oparta na porównaniach Kopia binarna struktura danych. Jest podobny do sortowanie przez wybór gdzie najpierw znajdujemy element minimalny i umieszczamy element minimalny na początku. Powtórz ten sam proces dla pozostałych elementów.
Algorytm sortowania sterty
Aby rozwiązać problem, postępuj zgodnie z poniższym pomysłem:
algorytm Kruskala
Zalecany problem Najpierw rozwiąż go w PRAKTYCE, zanim przejdziesz do rozwiązania Rozwiąż problemNajpierw przekonwertuj tablicę na strukturę danych sterty za pomocą heapify, następnie jeden po drugim usuń węzeł główny sterty Max i zastąp go ostatnim węzłem na stercie, a następnie umieść korzeń sterty na kopcu. Powtarzaj ten proces, aż rozmiar sterty będzie większy niż 1.
- Zbuduj stertę z podanej tablicy wejściowej.
- Powtarzaj poniższe kroki, aż sterta będzie zawierała tylko jeden element:
- Zamień element główny sterty (który jest największym elementem) z ostatnim elementem sterty.
- Usuń ostatni element sterty (który znajduje się teraz we właściwej pozycji).
- Złóż pozostałe elementy sterty.
- Posortowaną tablicę uzyskuje się poprzez odwrócenie kolejności elementów w tablicy wejściowej.
Szczegółowe działanie sortowania sterty
Aby lepiej zrozumieć sortowanie przez stertę, weźmy nieposortowaną tablicę i spróbujmy posortować ją za pomocą sortowania przez stertę.
Rozważmy tablicę: arr[] = {4, 10, 3, 5, 1}.Zbuduj kompletne drzewo binarne: Zbuduj kompletne drzewo binarne z tablicy.
Algorytm sortowania sterty | Zbuduj kompletne drzewo binarne
Przekształć w maksymalną stertę: Następnie zadaniem jest skonstruowanie drzewa z tej nieposortowanej tablicy i próba jego przekonwertowania maksymalna sterta.
- Aby przekształcić stertę w stertę maksymalną, węzeł nadrzędny powinien zawsze być większy lub równy węzłom podrzędnym
- Tutaj, w tym przykładzie, jako węzeł nadrzędny 4 jest mniejszy niż węzeł podrzędny 10, w związku z tym zamień je, aby zbudować maksymalną stertę.
- Teraz, 4 jako rodzic jest mniejszy od dziecka 5 , zamień je ponownie, a wynikowa sterta i tablica powinny wyglądać następująco:
Algorytm sortowania sterty | Max Heapify skonstruował drzewo binarne
Wykonaj sortowanie sterty: W każdym kroku usuń maksymalny element (tj. przesuń go do pozycji końcowej i usuń), a następnie rozważ pozostałe elementy i przekształć je w maksymalną stertę.
- Usuń element główny (10) z maksymalnej sterty. Aby usunąć ten węzeł, spróbuj zamienić go z ostatnim węzłem, tj. (1). Po usunięciu elementu głównego ponownie go złóż, aby przekonwertować go na maksymalną stertę.
- Wynikowa sterta i tablica powinny wyglądać następująco:
Algorytm sortowania sterty | Usuń maksimum z roota i max heapify
kody błędów Linuksa
- Powtórz powyższe kroki, a będzie to wyglądało następująco:
Algorytm sortowania sterty | Usuń następne maksimum z korzenia i max heapify
- Teraz ponownie usuń root (tj. 3) i wykonaj heapify.
Algorytm sortowania sterty | Powtórz poprzedni krok
- Teraz, gdy korzeń zostanie usunięty ponownie, zostanie on posortowany. i posortowana tablica będzie podobna tablica [] = {1, 3, 4, 5, 10} .
Algorytm sortowania sterty | Ostateczna posortowana tablica
Implementacja sortowania sterty
C++ // C++ program for implementation of Heap Sort #include using namespace std; // To heapify a subtree rooted with node i // which is an index in arr[]. // n is size of heap void heapify(int arr[], int N, int i) { // Initialize largest as root int largest = i; // left = 2*i + 1 int l = 2 * i + 1; // right = 2*i + 2 int r = 2 * i + 2; // If left child is larger than root if (l < N && arr[l]>arr[największy]) największy = l; // Jeśli prawe dziecko jest większe od największego // jak dotąd if (r< N && arr[r]>arr[największy]) największy = r; // Jeśli największy nie jest rootem if (największy != i) { swap(arr[i], arr[largest]); // Rekursywnie kopiuj dotknięte // poddrzewo heapify(arr, N, największy); } } // Główna funkcja sortująca stertę void heapSort(int arr[], int N) { // Buduj stertę (zmieniaj układ tablicy) for (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // Jeden po drugim wyodrębnij element ze sterty for (int i = N - 1; i> 0; i--) { // Przenieś bieżący katalog główny na koniec swap(arr[0], arr[i]); // wywołaj max heapify na zmniejszonej stercie heapify(arr, i, 0); } } // Funkcja narzędziowa wyświetlająca tablicę o rozmiarze n void printArray(int arr[], int N) { for (int i = 0; i< N; ++i) cout << arr[i] << ' '; cout << '
'; } // Driver's code int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call heapSort(arr, N); cout << 'Sorted array is
'; printArray(arr, N); }> C // Heap Sort in C #include // Function to swap the position of two elements void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // To heapify a subtree rooted with node i // which is an index in arr[]. // n is size of heap void heapify(int arr[], int N, int i) { // Find largest among root, // left child and right child // Initialize largest as root int largest = i; // left = 2*i + 1 int left = 2 * i + 1; // right = 2*i + 2 int right = 2 * i + 2; // If left child is larger than root if (left < N && arr[left]>arr[największy]) największy = lewy; // Jeśli prawe dziecko jest większe od największego // jak dotąd if (right< N && arr[right]>arr[największy]) największy = prawy; // Zamień i kontynuuj kopiowanie // jeśli pierwiastek nie jest największy // Jeśli największy nie jest pierwiastkiem if (największy != i) { swap(&arr[i], &arr[largest]); // Rekursywnie kopiuj dotknięte // poddrzewo heapify(arr, N, największy); } } // Główna funkcja sortująca stertę void heapSort(int arr[], int N) { // Buduj maksymalną stertę dla (int i = N / 2 - 1; i>= 0; i--) heapify(arr , N, i); // Sortowanie sterty dla (int i = N - 1; i>= 0; i--) { swap(&arr[0], &arr[i]); // Przenieś element główny //, aby uzyskać najwyższy element w // katalogu głównym ponownie heapify(arr, i, 0); } } // Funkcja narzędziowa wyświetlająca tablicę o rozmiarze n void printArray(int arr[], int N) { for (int i = 0; i< N; i++) printf('%d ', arr[i]); printf('
'); } // Driver's code int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call heapSort(arr, N); printf('Sorted array is
'); printArray(arr, N); } // This code is contributed by _i_plus_plus_.> Jawa // Java program for implementation of Heap Sort public class HeapSort { public void sort(int arr[]) { int N = arr.length; // Build heap (rearrange array) for (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // Jeden po drugim wyodrębnij element ze sterty for (int i = N - 1; i> 0; i--) { // Przenieś bieżący katalog główny na koniec int temp = arr[0]; tablica[0] = tablica[i]; arr[i] = temperatura; // wywołaj max heapify na zmniejszonej stercie heapify(arr, i, 0); } } // Aby utworzyć stertę poddrzewa zakorzenionego w węźle i, który jest // indeksem w arr[]. n to rozmiar sterty void heapify(int arr[], int N, int i) { int największy = i; // Zainicjuj największy jako pierwiastek int l = 2 * i + 1; // lewy = 2*i + 1 int r = 2 * i + 2; //right = 2*i + 2 // Jeśli lewe dziecko jest większe od pierwiastka if (l< N && arr[l]>arr[największy]) największy = l; // Jeśli prawe dziecko jest większe niż największe do tej pory if (r< N && arr[r]>arr[największy]) największy = r; // Jeśli największy nie jest rootem if (największy != i) { int swap = arr[i]; arr[i] = arr[największy]; arr[największy] = zamień; // Rekursywnie kopiuj poddrzewo, którego to dotyczy, heapify(arr, N, największy); } } /* Funkcja narzędziowa wyświetlająca tablicę o rozmiarze n */ static void printArray(int arr[]) { int N = arr.length; for (int i = 0; tj< N; ++i) System.out.print(arr[i] + ' '); System.out.println(); } // Driver's code public static void main(String args[]) { int arr[] = { 12, 11, 13, 5, 6, 7 }; int N = arr.length; // Function call HeapSort ob = new HeapSort(); ob.sort(arr); System.out.println('Sorted array is'); printArray(arr); } }> C# // C# program for implementation of Heap Sort using System; public class HeapSort { public void sort(int[] arr) { int N = arr.Length; // Build heap (rearrange array) for (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // Jeden po drugim wyodrębnij element ze sterty for (int i = N - 1; i> 0; i--) { // Przenieś bieżący katalog główny na koniec int temp = arr[0]; tablica[0] = tablica[i]; arr[i] = temperatura; // wywołaj max heapify na zmniejszonej stercie heapify(arr, i, 0); } } // Aby utworzyć stertę poddrzewa zakorzenionego w węźle i, który jest // indeksem w arr[]. n to rozmiar sterty void heapify(int[] arr, int N, int i) { int największy = i; // Zainicjuj największy jako pierwiastek int l = 2 * i + 1; // lewy = 2*i + 1 int r = 2 * i + 2; //right = 2*i + 2 // Jeśli lewe dziecko jest większe od pierwiastka if (l< N && arr[l]>arr[największy]) największy = l; // Jeśli prawe dziecko jest większe niż największe do tej pory if (r< N && arr[r]>arr[największy]) największy = r; // Jeśli największy nie jest rootem if (największy != i) { int swap = arr[i]; arr[i] = arr[największy]; arr[największy] = zamień; // Rekursywnie kopiuj poddrzewo, którego to dotyczy, heapify(arr, N, największy); } } /* Funkcja narzędziowa wyświetlająca tablicę o rozmiarze n */ static void printArray(int[] arr) { int N = arr.Length; for (int i = 0; tj< N; ++i) Console.Write(arr[i] + ' '); Console.Read(); } // Driver's code public static void Main() { int[] arr = { 12, 11, 13, 5, 6, 7 }; int N = arr.Length; // Function call HeapSort ob = new HeapSort(); ob.sort(arr); Console.WriteLine('Sorted array is'); printArray(arr); } } // This code is contributed // by Akanksha Rai(Abby_akku)> JavaScript // JavaScript program for implementation // of Heap Sort function sort( arr) { var N = arr.length; // Build heap (rearrange array) for (var i = Math.floor(N / 2) - 1; i>= 0; i--) heapify(arr, N, i); // Jeden po drugim wyodrębnij element ze sterty for (var i = N - 1; i> 0; i--) { // Przenieś bieżący katalog główny na koniec var temp = arr[0]; tablica[0] = tablica[i]; arr[i] = temperatura; // wywołaj max heapify na zmniejszonej stercie heapify(arr, i, 0); } } // Aby utworzyć stertę poddrzewa zakorzenionego w węźle i, który jest // indeksem w arr[]. n to rozmiar funkcji sterty heapify(arr, N, i) { var największy = i; // Zainicjuj największy jako pierwiastek var l = 2 * i + 1; // lewy = 2*i + 1 var r = 2 * i + 2; //right = 2*i + 2 // Jeśli lewe dziecko jest większe od pierwiastka if (l< N && arr[l]>arr[największy]) największy = l; // Jeśli prawe dziecko jest większe niż największe do tej pory if (r< N && arr[r]>arr[największy]) największy = r; // Jeśli największy nie jest rootem if (największy != i) { var swap = arr[i]; arr[i] = arr[największy]; arr[największy] = zamień; // Rekursywnie kopiuj poddrzewo, którego to dotyczy, heapify(arr, N, największy); } } /* Funkcja narzędziowa wyświetlająca tablicę o rozmiarze n */function printArray(arr) { var N = arr.length; dla (var i = 0; tj< N; ++i) document.write(arr[i] + ' '); } var arr = [12, 11, 13, 5, 6, 7]; var N = arr.length; sort(arr); document.write( 'Sorted array is'); printArray(arr, N); // This code is contributed by SoumikMondal> PHP // Php program for implementation of Heap Sort // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap function heapify(&$arr, $N, $i) { $largest = $i; // Initialize largest as root $l = 2*$i + 1; // left = 2*i + 1 $r = 2*$i + 2; // right = 2*i + 2 // If left child is larger than root if ($l < $N && $arr[$l]>$arr[$największy]) $największy = $l; // Jeśli prawe dziecko jest większe niż największe do tej pory if ($r< $N && $arr[$r]>$arr[$największy]) $największy = $r; // Jeśli największy nie jest rootem if ($largest != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$największy]; $arr[$największy] = $zamiana; // Rekursywnie kopiuj poddrzewo, którego dotyczy problem, heapify($arr, $N, $largest); } } // główna funkcja wykonująca funkcję sortowania sterty heapSort(&$arr, $N) { // Budowa sterty (przestawianie tablicy) dla ($i = $N / 2 - 1; $i>= 0; $i- -) heapify($arr, $N, $i); // Jeden po drugim wyodrębnij element ze sterty for ($i = $N-1; $i> 0; $i--) { // Przenieś bieżący katalog główny na koniec $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $temp; // wywołaj max heapify na zmniejszonej stercie heapify($arr, $i, 0); } } /* Funkcja narzędziowa wyświetlająca tablicę o rozmiarze n */function printArray(&$arr, $N) { for ($i = 0; $i< $N; ++$i) echo ($arr[$i].' ') ; } // Driver's program $arr = array(12, 11, 13, 5, 6, 7); $N = sizeof($arr)/sizeof($arr[0]); // Function call heapSort($arr, $N); echo 'Sorted array is ' . '
'; printArray($arr , $N); // This code is contributed by Shivi_Aggarwal ?>> Python3 # Python program for implementation of heap Sort # To heapify subtree rooted at index i. # n is size of heap def heapify(arr, N, i): largest = i # Initialize largest as root l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 # See if left child of root exists and is # greater than root if l < N and arr[largest] < arr[l]: largest = l # See if right child of root exists and is # greater than root if r < N and arr[largest] < arr[r]: largest = r # Change root, if needed if largest != i: arr[i], arr[largest] = arr[largest], arr[i] # swap # Heapify the root. heapify(arr, N, largest) # The main function to sort an array of given size def heapSort(arr): N = len(arr) # Build a maxheap. for i in range(N//2 - 1, -1, -1): heapify(arr, N, i) # One by one extract elements for i in range(N-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # swap heapify(arr, i, 0) # Driver's code if __name__ == '__main__': arr = [12, 11, 13, 5, 6, 7] # Function call heapSort(arr) N = len(arr) print('Sorted array is') for i in range(N): print('%d' % arr[i], end=' ') # This code is contributed by Mohit Kumra> Wyjście
Sorted array is 5 6 7 11 12 13>
Analiza złożoności Sortowanie sterty
Złożoność czasowa: O(N log N)
Przestrzeń pomocnicza: O(log n), ze względu na rekurencyjny stos wywołań. Jednakże przestrzeń pomocnicza może mieć wartość O(1) w przypadku implementacji iteracyjnej.
Ważne uwagi dotyczące sortowania sterty:
- Sortowanie sterty to algorytm lokalny.
- Jego typowa implementacja nie jest stabilna, ale można ją ustabilizować (patrz Ten )
- Zwykle 2-3 razy wolniej niż dobrze zaimplementowane Szybkie sortowanie . Powodem powolności jest brak lokalizacji odniesienia.
Zalety sortowania sterty:
- Efektywna złożoność czasowa: Sortowanie sterty ma we wszystkich przypadkach złożoność czasową O(n log n). Dzięki temu jest skuteczny w sortowaniu dużych zbiorów danych. The log nr współczynnik pochodzi z wysokości sterty binarnej i zapewnia dobrą wydajność algorytmu nawet przy dużej liczbie elementów.
- Zużycie pamięci - Użycie pamięci może być minimalne (poprzez napisanie iteracyjnej metody heapify() zamiast rekurencyjnej). Zatem poza tym, co jest niezbędne do przechowywania początkowej listy elementów do posortowania, nie potrzebuje ona do działania dodatkowej pamięci
- Prostota – Jest łatwiejszy do zrozumienia niż inne równie wydajne algorytmy sortowania, ponieważ nie wykorzystuje zaawansowanych koncepcji informatycznych, takich jak rekurencja.
Wady sortowania sterty:
- Kosztowny : Sortowanie na stercie jest kosztowne, ponieważ stałe są wyższe w porównaniu z sortowaniem przez scalanie, nawet jeśli złożoność czasowa wynosi O(n Log n) w obu przypadkach.
- Nietrwały : Sortowanie sterty jest niestabilne. Może to zmienić względną kolejność.
- Wydajny: Sortowanie sterty nie jest zbyt wydajne podczas pracy z bardzo złożonymi danymi.
Często zadawane pytania dotyczące sortowania sterty
Pytanie 1. Jakie są dwie fazy sortowania sterty?
Algorytm sortowania sterty składa się z dwóch faz. W pierwszej fazie tablica jest konwertowana na maksymalną stertę. W drugiej fazie usuwany jest najwyższy element (tj. ten u korzenia drzewa), a pozostałe elementy wykorzystywane są do utworzenia nowego maksymalnego kopca.
Pytanie 2. Dlaczego sortowanie sterty nie jest stabilne?
Algorytm sortowania sterty nie jest algorytmem stabilnym, ponieważ w funkcji heapSort() zamieniamy arr[i] z arr[0], co może zmienić względną kolejność równoważnych kluczy.
Pytanie 3. Czy sortowanie stosów jest przykładem algorytmu „Dziel i zwyciężaj”?
połączenia w Javie
Sortowanie sterty jest NIE w ogóle algorytm „Dziel i rządź”. Używa struktury danych sterty do wydajnego sortowania elementów, a nie metody dziel i zwyciężaj do sortowania elementów.
Pytanie 4. Który algorytm sortowania jest lepszy – sortowanie przez stertę czy sortowanie przez scalanie?
Odpowiedź leży w porównaniu ich złożoności czasowej i wymagań przestrzennych. Sortowanie przez scalanie jest nieco szybsze niż sortowanie przez stertę. Ale z drugiej strony sortowanie przez scalanie wymaga dodatkowej pamięci. W zależności od wymagań należy wybrać, którego z nich użyć.
Pytanie 5. Dlaczego sortowanie stertowe jest lepsze niż sortowanie przez wybór?
Sortowanie na stercie jest podobne do sortowania przez wybór, ale zapewnia lepszy sposób uzyskania maksymalnego elementu. Wykorzystuje strukturę danych sterty, aby uzyskać maksymalny element w stałym czasie