I denne opplæringen lærer du hvordan algoritmen til sortering fungerer. Du vil også finne eksempler på heap i C, C ++, Java og Python.
Heap Sort er en populær og effektiv sorteringsalgoritme innen dataprogrammering. Å lære å skrive haugsorteringsalgoritmen krever kunnskap om to typer datastrukturer - matriser og trær.
Det opprinnelige settet med tall som vi vil sortere, lagres i en matrise, for eksempel, (10, 3, 76, 34, 23, 32)og etter sortering får vi en sortert matrise(3,10,23,32,34,76)
Heap sort fungerer ved å visualisere elementene i matrisen som en spesiell type komplett binært tre som kalles en haug.
Som en forutsetning må du vite om et komplett binært tre- og dyddatastruktur.
Forholdet mellom matriseindekser og treelementer
Et komplett binært tre har en interessant egenskap som vi kan bruke til å finne barn og foreldre til hvilken som helst node.
Hvis indeksen til et element i matrisen er i, blir elementet i indeksen 2i+1det venstre barnet og elementet i 2i+2indeksen blir det rette barnet. Også overordnet til ethvert element ved indeks i er gitt av den nedre grensen av (i-1)/2.
Forholdet mellom matrise- og dyngdeindekser
La oss teste det ut,
Venstre barn av 1 (indeks 0) = element i (2 * 0 + 1) indeks = element i 1 indeks = 12 Høyre barn av 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øyre barn på 12 = element i (2 * 1 + 2) indeks = element i 4 indeks = 6
La oss også bekrefte at reglene gjelder for å finne foreldre til en hvilken som helst node
Forelder til 9 (posisjon 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indeks = 1 Forelder til 12 (posisjon 1) = (1-1) / 2 = 0 indeks = 1
Å forstå denne kartleggingen av matriseindekser til treposisjoner er avgjørende for å forstå hvordan Heap-datastrukturen fungerer og hvordan den brukes til å implementere Heap Sort.
Hva er Heap Data Structure?
Heap er en spesiell trebasert datastruktur. Et binært tre sies å følge en haugdatastruktur hvis
- det er et komplett binært tre
- Alle noder i treet følger egenskapen at de er større enn sine barn, dvs. det største elementet er ved roten og både dets barn og mindre enn roten og så videre. En slik haug kalles en maks-haug. Hvis i stedet alle noder er mindre enn barna deres, kalles det en min-haug
Følgende eksempeldiagram viser Max-Heap og Min-Heap.
Max Heap og Min Heap
Hvis du vil lære mer om det, kan du gå til Heap Data Structure.
Hvordan "heapify" et tre
Fra et komplett binært tre kan vi endre det til å bli en Max-Heap ved å kjøre en funksjon kalt heapify på alle ikke-bladelementene i haugen.
Siden heapify bruker rekursjon, kan det være vanskelig å forstå. Så la oss først tenke på hvordan du ville heapify et tre med bare 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 basissaker
Eksemplet ovenfor viser to scenarier - ett der roten er det største elementet og vi ikke trenger å gjøre noe. Og en annen der roten hadde et større element som barn, og vi trengte å bytte for å opprettholde maksimal haugegenskap.
Hvis du har jobbet med rekursive algoritmer før, har du sannsynligvis identifisert at dette må være basissaken.
La oss nå tenke på et annet scenario der det er mer enn ett nivå.
Hvordan heapify rotelement når undertrærne allerede er maksimale bunker
Toppelementet er ikke en maks-haug, men alle under-trærne er maks-hauger.
For å opprettholde maksimal haugegenskapen for hele treet, må vi fortsette å skyve 2 nedover til det når riktig posisjon.
Hvordan heapify rotelement når undertrær er max-heaps
For å opprettholde maks-haugegenskapen i et tre der begge undertrær er maksimale hauger, må vi kjøre heapify på rotelementet gjentatte ganger til det er større enn sine barn eller det blir en bladnode.
Vi kan kombinere begge disse forholdene i en heapify-funksjon 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 funksjonen fungerer både for basissaken og for et tre i alle størrelser. Vi kan dermed flytte rotelementet til riktig posisjon for å opprettholde maks-haug-status for hvilken som helst trestørrelse så lenge under-trærne er maks-hauger.
Bygg max-heap
For å bygge en maks-heap fra hvilket som helst tre, kan vi dermed begynne å heapify hvert under-tre fra bunnen opp og ende opp med en max-heap etter at funksjonen er brukt på alle elementene inkludert rotelementet.
Når det gjelder et komplett tre, blir den første indeksen til en ikke-bladnode gitt av n/2 - 1. Alle andre noder etter det er bladnoder og trenger derfor ikke å bli heapified.
Så vi kan bygge en maksimal haug som
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Lag matrise og beregne i 
Fremgangsmåte for å bygge maks heap for heap sort 
Trinn for å bygge maks heap for heap sort 
Trinn for å bygge maks heap for heap sort
Som vist i diagrammet ovenfor, begynner vi med å samle de laveste minste trærne og beveger oss gradvis opp til vi når rotelementet.
Hvis du har forstått alt til her, gratulerer, er du på vei til å mestre Heap-sorten.
Hvordan fungerer sortering?
- Siden treet tilfredsstiller Max-Heap-egenskapen, lagres det største elementet på rotnoden.
- Bytt: Fjern rotelementet og sett på slutten av matrisen (nte posisjon) Sett det siste elementet i treet (dyngen) på det ledige stedet.
- Fjern: Reduser størrelsen på dyngen med 1.
- Heapify: Heapify rotelementet igjen slik at vi har det høyeste elementet ved roten.
- Prosessen gjentas til alle elementene i listen er sortert.
Bytt, fjern og Heapify
Koden nedenfor viser operasjonen.
// 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 tilfeller (best case, gjennomsnittlig case og worst case).
La oss forstå grunnen til det. Høyden på et komplett binært tre som inneholder n elementer erlog n
Som vi har sett tidligere, må vi fortsette å sammenligne elementet med venstre og høyre barn og skyve det nedover til det når et punkt der begge barna er mindre enn det, for å fullstendig heapifisere et element hvis undertrær allerede er maks.
I verste fall vil vi trenge å flytte et element fra roten til bladnoden og gjøre et mangfold av log(n)sammenligninger og bytter.
I løpet av build_max_heap-fasen gjør vi det for n/2elementer, så det verste tilfelle er kompleksiteten til build_heap-trinnet n/2*log n ~ nlog n.
Under sorteringstrinnet bytter vi rotelementet med det siste elementet og heapify rotelementet. For hvert element tar dette igjen den log nverste tiden fordi vi kanskje må bringe elementet helt fra roten til bladet. Siden vi gjentar dette n ganger, er heap_sort trinnet også nlog n.
Også siden build_max_heapog heap_sorttrinnene blir utført en etter en, blir den algoritmiske kompleksitet ikke multipliseres, og den forblir i størrelsesorden nlog n.
Også den utfører sortering i O(1)romkompleksitet. Sammenlignet med Quick Sort har den en bedre verste sak ( O(nlog n) ). Quick Sort har kompleksitet O(n^2)i verste fall. Men i andre tilfeller er Quick Sort rask. Introsort er et alternativ til heapsort som kombinerer quicksort og heapsort for å opprettholde fordelene med begge deler: worst case hastighet på heapsort og gjennomsnittlig hastighet på quicksort.
Heap Sorter applikasjoner
Systemer som er opptatt av sikkerhet og innebygde systemer som Linux Kernel bruker Heap Sort på grunn av O(n log n)øvre grense på Heapsorts kjøretid og konstant O(1)øvre grense på hjelpelagring.
Selv om Heap Sort har O(n log n)tidskompleksitet selv i verste fall, har den ikke flere applikasjoner (sammenlignet med andre sorteringsalgoritmer som Quick Sort, Merge Sort). Imidlertid kan den underliggende datastrukturen, heap, brukes effektivt hvis vi ønsker å trekke ut den minste (eller største) fra listen over varer uten at det er kostnad å holde de gjenværende elementene i sortert rekkefølge. For eksempel Prioritetskøer.
