I denne vejledning lærer du, hvordan bunksorteringsalgoritme fungerer. Du finder også arbejdseksempler på heap-sortering i C, C ++, Java og Python.
Heap Sort er en populær og effektiv sorteringsalgoritme inden for computerprogrammering. At lære at skrive bugsorteringsalgoritmen kræver viden om to typer datastrukturer - arrays og træer.
Det oprindelige sæt numre, som vi vil sortere, gemmes i en matrix, fx (10, 3, 76, 34, 23, 32)og efter sortering får vi en sorteret matrix(3,10,23,32,34,76)
Heap-sort fungerer ved at visualisere elementerne i arrayet som en speciel slags komplet binært træ kaldet en bunke.
Som en forudsætning skal du vide om et komplet datastruktur for binært træ og bunke.
Forholdet mellem matrixindekser og træelementer
Et komplet binært træ har en interessant egenskab, som vi kan bruge til at finde børn og forældre til enhver knude.
Hvis indekset for et hvilket som helst element i matrixen er i, bliver elementet i indekset 2i+1det venstre barn, og elementet i 2i+2indekset bliver det rigtige barn. Også overordnet til ethvert element ved indeks i er givet af den nedre grænse for (i-1)/2.
Forholdet mellem array- og bunkeindekser
Lad os teste det ud,
Venstre barn af 1 (indeks 0) = element i (2 * 0 + 1) indeks = element i 1 indeks = 12 Højre barn af 1 = element i (2 * 0 + 2) indeks = element i 2 indeks = 9 Tilsvarende Venstre barn på 12 (indeks 1) = element i (2 * 1 + 1) indeks = element i 3 indeks = 5 Højre barn på 12 = element i (2 * 1 + 2) indeks = element i 4 indeks = 6
Lad os også bekræfte, at reglerne gælder for at finde forælder til enhver node
Forælder til 9 (position 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indeks = 1 Forælder til 12 (position 1) = (1-1) / 2 = 0 indeks = 1
At forstå denne kortlægning af matrixindekser til træpositioner er afgørende for at forstå, hvordan Heap-datastrukturen fungerer, og hvordan den bruges til at implementere Heap Sort.
Hvad er Heap-datastruktur?
Heap er en speciel træbaseret datastruktur. Et binært træ siges at følge en bunke datastruktur, hvis
- det er et komplet binært træ
- Alle noder i træet følger egenskaben, at de er større end deres børn, dvs. det største element er ved roden og både dets børn og mindre end roden og så videre. En sådan bunke kaldes en max-bunke. Hvis i stedet alle noder er mindre end deres børn, kaldes det en min-bunke
Følgende eksempeldiagram viser Max-Heap og Min-Heap.
Max Heap og Min Heap
For at lære mere om det, besøg Heap Data Structure.
Sådan "heapificeres" et træ
Fra et komplet binært træ kan vi ændre det til at blive en Max-Heap ved at køre en funktion kaldet heapify på alle bunkeelementerne.
Da heapify bruger rekursion, kan det være svært at forstå. Så lad os først tænke på, hvordan du ville heapify et træ med kun tre elementer.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Heapify basissager
Eksemplet ovenfor viser to scenarier - hvor roten er det største element, og vi behøver ikke at gøre noget. Og en anden, hvor roden havde et større element som barn, og vi havde brug for at bytte for at opretholde max-heap-ejendom.
Hvis du har arbejdet med rekursive algoritmer før, har du sandsynligvis identificeret, at dette skal være basissagen.
Lad os nu tænke på et andet scenario, hvor der er mere end et niveau.
Sådan heapificeres rodelementet, når dets undertræer allerede er maksimale bunker
Det øverste element er ikke en maks-bunke, men alle undertræer er max-bunker.
For at opretholde den maksimale bunkeegenskab for hele træet skal vi fortsætte med at skubbe 2 nedad, indtil det når sin korrekte position.
Sådan heapificeres rodelementet, når dets undertræer er max-heaps
For at opretholde max-heap-egenskaben i et træ, hvor begge undertræer er max-heaps, skal vi køre heapify på rodelementet gentagne gange, indtil det er større end dets børn, eller det bliver en bladknude.
Vi kan kombinere begge disse betingelser i en heapify-funktion som
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); ) )
Denne funktion fungerer både til basissagen og til et træ af enhver størrelse. Vi kan således flytte rodelementet til den rigtige position for at opretholde maksimum-bunke-status for enhver træstørrelse, så længe undertræerne er max-bunker.
Byg max-bunke
For at opbygge en max-heap fra et hvilket som helst træ kan vi således begynde at heapify hvert sub-tree fra bunden op og ende med en max-heap, efter at funktionen er anvendt på alle elementerne inklusive rodelementet.
I tilfælde af et komplet træ er det første indeks for en ikke-bladknude givet af n/2 - 1. Alle andre noder efter det er bladnoder og behøver derfor ikke at blive heapificeret.
Så vi kan bygge en maksimal bunke som
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Opret matrix og beregne i 
Trin til at bygge maks. Bunke til bunnsortering 
Trin til at bygge maks. Bunke til bunke sortering 
Trin til at bygge maksimal bunke til bunke sortering
Som vist i ovenstående diagram starter vi med at samle de laveste mindste træer op og gradvist bevæger os op, indtil vi når rodelementet.
Hvis du har forstået alt indtil her, tillykke, er du på vej til at mestre Heap-sorteringen.
Hvordan fungerer sortering af dynger?
- Da træet opfylder Max-Heap-ejendommen, gemmes det største element i rodnoden.
- Byt: Fjern rodelementet og placer i slutningen af arrayet (n. Position) Sæt det sidste element i træet (bunken) på det ledige sted.
- Fjern: Reducer bunken med 1.
- Heapify: Heapify rodelementet igen, så vi har det højeste element ved root.
- Processen gentages, indtil alle elementerne på listen er sorteret.
Byt, fjern og Heapify
Koden nedenfor viser handlingen.
// 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); )
Python, Java og C / C ++ eksempler
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); )
Heap Sort Complexity
Heap Sort har O(nlog n)tidskompleksitet for alle sager (i bedste fald, gennemsnit og værste tilfælde).
Lad os forstå grunden til det. Højden på et komplet binært træ, der indeholder n elementer, erlog n
Som vi har set tidligere, skal vi fortsætte med at sammenligne elementet med dets venstre og højre børn og skubbe det nedad, indtil det når et punkt, hvor begge dets børn er mindre end det for fuldt at heapificere et element, hvis undertræer allerede er max-bunke.
I værste fald bliver vi nødt til at flytte et element fra roden til bladknuden ved at lave et multipel af log(n)sammenligninger og swaps.
I løbet af build_max_heap-scenen gør vi det for n/2elementer, så den værste tilfælde er kompleksiteten af build_heap-trinnet n/2*log n ~ nlog n.
Under sorteringstrinnet udveksler vi rodelementet med det sidste element og heapify rodelementet. For hvert element tager dette igen den log nværste tid, fordi vi måske bliver nødt til at bringe elementet hele vejen fra roden til bladet. Da vi gentager dette n gange, er heap_sort-trinnet også nlog n.
Også da build_max_heapog heap_sorttrinene udføres efter hinanden, multipliceres den algoritmiske kompleksitet ikke, og den forbliver i rækkefølgen af nlog n.
Det udfører også sortering i O(1)rumkompleksitet. Sammenlignet med Quick Sort har det en bedre worst case ( O(nlog n) ). Hurtig sortering er kompleks O(n^2)i værste fald. Men i andre tilfælde er Quick Sort hurtig. Introsort er et alternativ til heapsort, der kombinerer quicksort og heapsort for at bevare fordelene ved begge dele: worst case-hastighed for heapsort og gennemsnitshastighed for quicksort.
Heap Sort-applikationer
Systemer, der beskæftiger sig med sikkerhed og indlejrede systemer som Linux Kernel, bruger Heap Sort på grund af den O(n log n)øvre grænse for Heapsorts driftstid og den konstante O(1)øvre grænse for dens hjælpelagring.
Selvom Heap Sort har O(n log n)tidskompleksitet selv i værste fald, har den ikke flere applikationer (sammenlignet med andre sorteringsalgoritmer som Quick Sort, Merge Sort). Den underliggende datastruktur, heap, kan dog bruges effektivt, hvis vi ønsker at udtrække den mindste (eller største) fra listen over varer uden overhead for at holde de resterende varer i den sorterede rækkefølge. For eksempel Prioritetskøer.
