W tym samouczku dowiesz się, jak działa algorytm sortowania sterty. Znajdziesz również działające przykłady sortowania sterty w językach C, C ++, Java i Python.
Heap Sort to popularny i wydajny algorytm sortowania w programowaniu komputerowym. Nauka pisania algorytmu sortowania na stosie wymaga znajomości dwóch typów struktur danych - tablic i drzew.
Początkowy zbiór liczb, które chcemy posortować jest przechowywany w tablicy np. (10, 3, 76, 34, 23, 32)I po posortowaniu otrzymujemy posortowaną tablicę(3,10,23,32,34,76)
Sortowanie na stosie działa poprzez wizualizację elementów tablicy jako specjalnego rodzaju kompletnego drzewa binarnego zwanego stertą.
Warunkiem wstępnym jest znajomość pełnego drzewa binarnego i struktury danych sterty.
Związek między indeksami tablic i elementami drzewa
Kompletne drzewo binarne ma interesującą właściwość, której możemy użyć do znalezienia dzieci i rodziców dowolnego węzła.
Jeśli indeks dowolnego elementu w tablicy to i, element w indeksie 2i+1stanie się lewym dzieckiem, a element w 2i+2indeksie - prawym dzieckiem. Ponadto element nadrzędny dowolnego elementu o indeksie i jest określany przez dolną granicę (i-1)/2.
Relacja między indeksami tablicy i sterty
Przetestujmy to,
Lewe dziecko 1 (indeks 0) = element w (2 * 0 + 1) indeks = element w 1 indeksie = 12 Prawe dziecko 1 = element w (2 * 0 + 2) indeks = element w 2 indeksie = 9 Podobnie, Lewe dziecko 12 (indeks 1) = element w (2 * 1 + 1) indeks = element w 3 indeks = 5 Prawe dziecko 12 = element w (2 * 1 + 2) indeks = element w 4 indeks = 6
Potwierdźmy również, że obowiązują reguły wyszukiwania rodzica dowolnego węzła
Rodzic 9 (pozycja 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indeks = 1 Rodzic rodzic 12 (pozycja 1) = (1-1) / 2 = 0 indeks = 1
Zrozumienie tego odwzorowania indeksów tablic na pozycje drzewa ma kluczowe znaczenie dla zrozumienia, jak działa struktura danych sterty i jak jest wykorzystywana do implementacji sortowania sterty.
Co to jest struktura danych sterty?
Sterta to specjalna struktura danych oparta na drzewie. Mówi się, że drzewo binarne ma strukturę danych stosu, jeśli
- jest to kompletne drzewo binarne
- Wszystkie węzły w drzewie mają tę właściwość, że są większe niż ich dzieci, tj. Największy element znajduje się w korzeniu i oba jego dzieci oraz jest mniejszy od korzenia i tak dalej. Taka sterta nazywana jest stertą maksymalną. Jeśli zamiast tego wszystkie węzły są mniejsze niż ich dzieci, nazywa się to stertą min
Poniższy przykładowy diagram przedstawia Max-Heap i Min-Heap.
Max Heap i Min Heap
Aby dowiedzieć się więcej na ten temat, odwiedź stronę Struktura danych sterty.
Jak „usypać” drzewo
Zaczynając od pełnego drzewa binarnego, możemy go zmodyfikować, aby stał się Max-Heap, uruchamiając funkcję o nazwie heapify na wszystkich elementach sterty nie będących liśćmi.
Ponieważ heapify używa rekurencji, może to być trudne do uchwycenia. Zastanówmy się więc najpierw, jak uformować drzewo za pomocą zaledwie trzech elementów.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Podstawy heapify
Powyższy przykład pokazuje dwa scenariusze - jeden, w którym root jest największym elementem i nie musimy nic robić. I jeszcze jeden, w którym root miał większy element jako dziecko i musieliśmy się zamienić, aby zachować właściwość max-heap.
Jeśli wcześniej pracowałeś z algorytmami rekurencyjnymi, prawdopodobnie zidentyfikowałeś, że musi to być przypadek podstawowy.
Pomyślmy teraz o innym scenariuszu, w którym jest więcej niż jeden poziom.
Jak utworzyć stertę elementu głównego, gdy jego poddrzewa są już maksymalne
Górny element nie jest maksymalnym stosem, ale wszystkie poddrzewa to maksymalne stosy.
Aby zachować właściwość max-heap dla całego drzewa, będziemy musieli naciskać 2 w dół, aż osiągnie właściwą pozycję.
Jak ułożyć stos element główny, gdy jego poddrzewa są maksymalne
Tak więc, aby zachować właściwość max-heap w drzewie, w którym oba poddrzewa są max-heaps, musimy wielokrotnie uruchamiać heapify na elemencie głównym, aż będzie większy niż jego dzieci lub stanie się węzłem liścia.
Możemy połączyć oba te warunki w jednej funkcji sterty jako
void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) )
Ta funkcja działa zarówno dla przypadku podstawowego, jak i dla drzewa o dowolnym rozmiarze. W ten sposób możemy przesunąć element główny do właściwej pozycji, aby zachować maksymalny status sterty dla dowolnego rozmiaru drzewa, o ile poddrzewa są maksymalne.
Zbuduj max-heap
Aby zbudować stertę maksymalną z dowolnego drzewa, możemy w ten sposób rozpocząć stertę każdego poddrzewa od dołu do góry i skończyć z stertą maksymalną po zastosowaniu funkcji do wszystkich elementów, w tym elementu głównego.
W przypadku pełnego drzewa pierwszy indeks węzła nie będącego liściem podaje się przez n/2 - 1. Wszystkie inne węzły po tym są węzłami-liśćmi i dlatego nie muszą być ułożone na stosie.
Tak więc możemy zbudować maksymalną stertę jako
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Tworzenie tablicy i obliczanie i 
Kroki tworzenia maksymalnej sterty do sortowania sterty 
Kroki tworzenia maksymalnej sterty do sortowania sterty 
Kroki tworzenia maksymalnej sterty do sortowania sterty
Jak pokazano na powyższym diagramie, zaczynamy od ułożenia najniższych najmniejszych drzewek i stopniowo przesuwamy się w górę, aż dotrzemy do elementu głównego.
Jeśli do tej pory wszystko zrozumiałeś, gratulacje, jesteś na najlepszej drodze do opanowania gatunku Heap.
Jak działa sortowanie stosów?
- Ponieważ drzewo spełnia właściwość Max-Heap, największy element jest przechowywany w węźle głównym.
- Zamiana: Usuń element główny i umieść na końcu tablicy (n-ta pozycja) Umieść ostatni element drzewa (stertę) w wolnym miejscu.
- Usuń: zmniejsz rozmiar sterty o 1.
- Heapify: Heapify the root element ponownie, abyśmy mieli najwyższy element w root.
- Proces jest powtarzany, dopóki wszystkie pozycje listy nie zostaną posortowane.
Zamień, usuń i stosuj
Poniższy kod przedstawia operację.
// Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); )
Przykłady w Pythonie, Javie i C / C ++
Python Java C C ++ # Heap Sort in python def heapify(arr, n, i): # Find largest among root and children largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r # If root is not largest, swap with largest and continue heapifying if largest != i: arr(i), arr(largest) = arr(largest), arr(i) heapify(arr, n, largest) def heapSort(arr): n = len(arr) # Build max heap for i in range(n//2, -1, -1): heapify(arr, n, i) for i in range(n-1, 0, -1): # Swap arr(i), arr(0) = arr(0), arr(i) # Heapify root element heapify(arr, i, 0) arr = (1, 12, 9, 5, 6, 10) heapSort(arr) n = len(arr) print("Sorted array is") for i in range(n): print("%d " % arr(i), end='')
// Heap Sort in Java public class HeapSort ( public void sort(int arr()) ( int n = arr.length; // Build max heap for (int i = n / 2 - 1; i>= 0; i--) ( heapify(arr, n, i); ) // Heap sort for (int i = n - 1; i>= 0; i--) ( int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // Heapify root element heapify(arr, i, 0); ) ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l arr(largest)) largest = l; if (r arr(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( int swap = arr(i); arr(i) = arr(largest); arr(largest) = swap; heapify(arr, n, largest); ) ) // Function to print an array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver code public static void main(String args()) ( int arr() = ( 1, 12, 9, 5, 6, 10 ); HeapSort hs = new HeapSort(); hs.sort(arr); System.out.println("Sorted array is"); printArray(arr); ) )
// Heap Sort in C #include // Function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) ) // Main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) printf("%d ", arr(i)); printf(""); ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); printf("Sorted array is "); printArray(arr, n); )
// Heap Sort in C++ #include using namespace std; void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(arr(i), arr(largest)); heapify(arr, n, largest); ) ) // main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(arr(0), arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) cout << arr(i) << " "; cout << ""; ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); cout << "Sorted array is "; printArray(arr, n); )
Złożoność sortowania sterty
Sortowanie na stosie ma O(nlog n)złożoność czasową dla wszystkich przypadków (przypadek najlepszy, przypadek średni i przypadek najgorszy).
Zrozummy, dlaczego. Wysokość pełnego drzewa binarnego zawierającego n elementów wynosilog n
As we have seen earlier, to fully heapify an element whose subtrees are already max-heaps, we need to keep comparing the element with its left and right children and pushing it downwards until it reaches a point where both its children are smaller than it.
In the worst case scenario, we will need to move an element from the root to the leaf node making a multiple of log(n) comparisons and swaps.
During the build_max_heap stage, we do that for n/2 elements so the worst case complexity of the build_heap step is n/2*log n ~ nlog n.
During the sorting step, we exchange the root element with the last element and heapify the root element. For each element, this again takes log n worst time because we might have to bring the element all the way from the root to the leaf. Since we repeat this n times, the heap_sort step is also nlog n.
Also since the build_max_heap and heap_sort steps are executed one after another, the algorithmic complexity is not multiplied and it remains in the order of nlog n.
Also it performs sorting in O(1) space complexity. Compared with Quick Sort, it has a better worst case ( O(nlog n) ). Quick Sort has complexity O(n^2) for worst case. But in other cases, Quick Sort is fast. Introsort is an alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.
Heap Sort Applications
Systems concerned with security and embedded systems such as Linux Kernel use Heap Sort because of the O(n log n) upper bound on Heapsort's running time and constant O(1) upper bound on its auxiliary storage.
Chociaż Heap Sort ma O(n log n)złożoność czasową nawet w najgorszym przypadku, nie ma więcej aplikacji (w porównaniu z innymi algorytmami sortowania, takimi jak szybkie sortowanie, sortowanie przez scalanie). Jednak jego podstawowa struktura danych, heap, może być efektywnie wykorzystana, jeśli chcemy wyodrębnić najmniejszy (lub największy) z listy elementów bez narzutu związanego z utrzymywaniem pozostałych elementów w posortowanej kolejności. Na przykład kolejki priorytetowe.
