Selles õpetuses saate teada, kuidas hunniku sortimise algoritm töötab. Samuti leiate toimivaid näiteid kuhja sorteerimise kohta C, C ++, Java ja Python.
Heap Sort on populaarne ja tõhus sortimisalgoritm arvutiprogrammeerimisel. Hunniku sortimise algoritmi kirjutamise õppimine nõuab teadmisi kahte tüüpi andmestruktuuridest - massiividest ja puudest.
Esialgne numbrite komplekt, mida soovime sorteerida, salvestatakse massiivi nt (10, 3, 76, 34, 23, 32)ja pärast sortimist saame sorteeritud massiivi(3,10,23,32,34,76)
Hunniku sorteerimine visualiseerib massiivi elemente erilise tervikliku binaarse puuna, mida nimetatakse kuhjaks.
Eeldusena peate teadma täieliku binaarse puu ja kuhja andmestruktuuri kohta.
Massiivindeksite ja puuelementide suhe
Täielikul binaarsel puul on huvitav omadus, mida saame kasutada mis tahes sõlme laste ja vanemate leidmiseks.
Kui massiivi mis tahes elemendi indeks on i, saab indeksi 2i+1elemendist vasak laps ja 2i+2indeksi elemendist parem laps. Indeksi i mis tahes elemendi vanema annab ka alumine piir (i-1)/2.
Massiivi ja kuhjaindeksite seos
Proovime seda,
1 vasak laps (indeks 0) = element (2 * 0 + 1) indeksis = element 1 indeksis = 12 1 parempoolne laps = indeksi (2 * 0 + 2) element = indeksi 2 indeks = 9 Samamoodi Vasak 12-aastane laps (indeks 1) = element (2 * 1 + 1) indeksis = element 3-s indeksis = 5 Parem 12-aastane laps = element (2 * 1 + 2) indeksis = element 4-s
Kinnitagem ka seda, et reeglid kehtivad mis tahes sõlme vanema leidmiseks
9 lapse vanem (positsioon 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indeks = 1 12 lapse vanem (positsioon 1) = (1-1) / 2 = 0 indeks = 1
Massiivindeksite puupositsioonidele vastendamise mõistmine on ülioluline, et mõista, kuidas kuhja andmestruktuur töötab ja kuidas seda kasutatakse kuhja sortimise rakendamiseks.
Mis on kuhjaga andmete struktuur?
Heap on spetsiaalne puupõhine andmestruktuur. Binaarne puu järgib kuhja andmestruktuuri, kui
- see on täielik binaarne puu
- Kõik puu sõlmed järgivad omadust, et nad on suuremad kui nende lapsed, st suurim element on juures ja nii selle lastes kui ka väiksem kui juur ja nii edasi. Sellist kuhja nimetatakse max-kuhjaks. Kui selle asemel on kõik sõlmed väiksemad kui nende lapsed, nimetatakse seda minihunnikuks
Järgmine näidisdiagramm näitab Max-Heap ja Min-Heap.
Max Heap ja Min Heap
Selle kohta lisateabe saamiseks külastage lehte Heap Data Structure.
Kuidas puu "kuhjata"
Alustades täielikust binaarsest puust, saame seda muuta Max-Heapiks, käivitades funktsiooni nimega heapify kõikides kuhja mitte-lehelistes elementides.
Kuna heapify kasutab rekursiooni, võib sellest olla raske aru saada. Mõelgem siis kõigepealt sellele, kuidas saaksite kuhjata vaid kolme elemendiga puud.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Heapify juhtumeid
Ülaltoodud näide näitab kahte stsenaariumi - üks, kus juur on suurim element ja meil pole vaja midagi teha. Ja veel üks, kus juurel oli lapsena suurem element ja meil oli vaja vahetada, et säilitada maksimaalse kuhja omadus.
Kui olete varem rekursiivsete algoritmidega töötanud, olete tõenäoliselt tuvastanud, et see peab olema juhtum.
Mõelgem nüüd teisele stsenaariumile, kus on rohkem kui üks tase.
Kuidas juurelementi kuhjata, kui selle alampuud on juba maksimaalsed
Ülemine element ei ole max-hunnik, kuid kõik alampuud on max-hunnikud.
Max-kuhja omaduse säilitamiseks kogu puu jaoks peame pidevalt 2 allapoole suruma, kuni see jõuab õigesse asendisse.
Kuidas juurelementi kuhjata, kui selle alampuud on maksimaalsed
Seega, et säilitada maksimaalse kuhja omadus puul, kus mõlemad alampuud on maksimaalsed, peame korduvalt töötama juurelemendil, kuni see on suurem kui tema lapsed või sellest saab lehesõlm.
Mõlemad tingimused saame kombineerida ühes kuhjafunktsioonis
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); ) )
See funktsioon töötab nii alusjuhtumi kui ka igas suuruses puu puhul. Seega saame juurelemendi õigesse asendisse viia, et säilitada maksimaalse kuhja olek mis tahes puu suuruse jaoks, kui alampuud on maksimaalsed.
Ehita max-hunnik
Maksimaalse kuhja ehitamiseks igast puust võime seega hakata iga alampuud kuhjama alt üles ja lõpuks maksimaalse kuhjaga, kui funktsioon on rakendatud kõikidele elementidele, sealhulgas juurelemendile.
Tervikliku puu korral annab leheta sõlme esimese indeksi n/2 - 1. Kõik muud sõlmed pärast seda on lehesõlmed ja seega pole neid vaja kuhjata.
Niisiis, saame ehitada maksimaalse hunniku
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Loo massiiv ja arvuta i 
Sammud, et ehitada hunniku sorteerimise 
jaoks 
maksimaalne hunnik
Nagu ülaltoodud diagramm näitab, alustame kõige madalamate väikseimate puude kuhjamisega ja liigume järk-järgult ülespoole, kuni jõuame juurelemendini.
Kui olete siiani kõigest aru saanud, siis palju õnne, olete teel Heap sorti valdamisele.
Kuidas Heap sortimine töötab?
- Kuna puu rahuldab omadust Max-Heap, salvestatakse suurim element juursõlmesse.
- Vahetamine: Eemaldage juurelement ja asetage massiivi lõppu (n-s positsioon) Pange puu viimane osa (hunnik) vabasse kohta.
- Eemaldamine: vähendage kuhja suurust 1 võrra.
- Heapify: Heapify root element uuesti, nii et meil oleks kõrgeim element root.
- Protsessi korratakse seni, kuni kõik loendi üksused on sorteeritud.
Vaheta, eemalda ja kuhjata
Allolev kood näitab toimingut.
// 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); )
Pythoni, Java ja C / C ++ näited
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); )
Hunniku sorteerimise keerukus
Heap Sortil on O(nlog n)kõigi juhtumite jaoks ajaline keerukus (parim juhtum, keskmine juhtum ja halvim juhtum).
Mõistame põhjust, miks. N elementi sisaldava tervikliku kahendpuu kõrgus onlog 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.
Ehkki Heap Sortil on O(n log n)ka halvimal juhul keeruline aeg, pole sellel rohkem rakendusi (võrreldes teiste sortimisalgoritmidega, nagu Quick Sort, Merge Sort). Kuid selle aluseks olevat andmestruktuuri, hunnikut, saab tõhusalt kasutada, kui soovime eraldada üksuste loendist väikseima (või suurima), ilma et peaksime hoidma ülejäänud üksusi järjestatud järjestuses. Näiteks prioriteetsete järjekordade jaoks.
