V tomto výučbe sa dozviete, ako funguje algoritmus triedenia hromád. Nájdete tiež pracovné príklady triedenia hald v jazykoch C, C ++, Java a Python.
Heap Sort je populárny a efektívny algoritmus triedenia v počítačovom programovaní. Naučiť sa písať algoritmus triedenia haldy vyžaduje znalosť dvoch typov dátových štruktúr - polí a stromov.
Počiatočná množina čísel, ktorú chceme triediť, je uložená v poli napr. (10, 3, 76, 34, 23, 32)A po zoradení dostaneme zoradené pole(3,10,23,32,34,76)
Heap sort funguje tak, že vizualizuje prvky poľa ako špeciálny druh kompletného binárneho stromu nazývaného halda.
Ako nevyhnutná podmienka musíte vedieť o úplnej binárnom strome a hromadnej dátovej štruktúre.
Vzťah medzi indexmi polí a prvkami stromov
Kompletný binárny strom má zaujímavú vlastnosť, pomocou ktorej môžeme nájsť deti a rodičov ktoréhokoľvek uzla.
Ak je index ľubovoľného prvku v poli i, prvok v indexe 2i+1sa stane ľavým potomkom a prvok v 2i+2indexe sa stane pravým potomkom. Nadradený prvok ľubovoľného prvku v indexe i je tiež daný dolnou hranicou (i-1)/2.
Vzťah medzi indexmi poľa a haldy
Poďme to vyskúšať
Ľavé dieťa z 1 (index 0) = prvok v (2 * 0 + 1) index = prvok v 1 index = 12 Pravé dieťa z 1 = prvok v (2 * 0 + 2) index = prvok v 2 index = 9 Podobne, Ľavé dieťa 12 (index 1) = prvok v (2 * 1 + 1) index = prvok v 3 index = 5 Pravé dieťa 12 = prvok v (2 * 1 + 2) index = prvok v 4 index = 6
Potvrdíme tiež, že pravidlá platia pre vyhľadanie rodiča ktoréhokoľvek uzla
Rodič 9 (pozícia 2) = (2-1) / 2 = ½ = 0,5 ~ 0 index = 1 Rodič 12 (pozícia 1) = (1-1) / 2 = 0 index = 1
Pochopenie tohto mapovania indexov polí na pozície stromov je zásadné pre pochopenie toho, ako funguje dátová štruktúra haldy a ako sa používa na implementáciu triedenia haldy.
Čo je halda dátová štruktúra?
Halda je špeciálna stromová dátová štruktúra. O binárnom strome sa hovorí, že sleduje haldy dátovú štruktúru, ak
- je to kompletný binárny strom
- Všetky uzly v strome sledujú vlastnosť, že sú väčšie ako ich deti, tj. Najväčší prvok je v koreni a jeho podriadených prvkoch a menší ako koreň atď. Takáto halda sa nazýva max-halda. Ak sú všetky uzly menšie ako ich deti, nazýva sa to halda min
Nasledujúci príkladový diagram zobrazuje Max-Heap a Min-Heap.
Max. Halda a minimálna halda
Ak sa o tom chcete dozvedieť viac, navštívte haldu dátovej štruktúry.
Ako „heapifikovať“ strom
Počnúc úplným binárnym stromom ho môžeme upraviť tak, aby sa z neho stal Max-Heap, a to spustením funkcie nazvanej heapify na všetkých nelistových prvkoch haldy.
Pretože heapify používa rekurziu, je ťažké ho pochopiť. Najprv sa teda zamyslime nad tým, ako by ste heapifikovali strom iba s tromi prvkami.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Heapify základné prípady
Vyššie uvedený príklad ukazuje dva scenáre - jeden, v ktorom je root najväčší prvok a nemusíme nič robiť. A ďalší, v ktorom mal root ako dieťa väčší prvok a potrebovali sme ho vymeniť, aby sme zachovali vlastnosť max-heap.
Ak ste predtým pracovali s rekurzívnymi algoritmami, pravdepodobne ste zistili, že to musí byť základný prípad.
Teraz si predstavme ďalší scenár, v ktorom existuje viac ako jedna úroveň.
Ako heapify root element, keď jeho podstromy sú už max
Vrchný prvok nie je maximálna hromada, ale všetky podkategórie sú maximálnymi hromadami.
Aby sme zachovali vlastnosť max-heap pre celý strom, budeme musieť tlačiť 2 smerom nadol, kým nedosiahne svoju správnu pozíciu.
Ako heapify root element, keď jeho podstromy sú max-haldy
Aby sme teda udržali vlastnosť max-heap v strome, kde sú obidva podrodiny max-haldy, musíme opakovane spúšťať heapify na koreňovom prvku, kým nie je väčší ako jeho deti alebo sa nestane uzlom listu.
Môžeme kombinovať obe tieto podmienky v jednej funkcii heapify ako
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); ) )
Táto funkcia funguje pre základný prípad aj pre strom akejkoľvek veľkosti. Môžeme teda presunúť koreňový prvok do správnej polohy, aby sme udržali stav maximálnej haldy pre ľubovoľnú veľkosť stromu, pokiaľ sú podstromy maximálnymi hromadami.
Postavte maximálnu hromadu
Ak chcete vytvoriť maximálnu hromadu z ľubovoľného stromu, môžeme začať hromadiť každý podstrom zdola nahor a po použití funkcie na všetky prvky vrátane koreňového prvku skončiť s maximálnou hromadou.
V prípade úplného stromu je prvý index nelistového uzla daný znakom n/2 - 1. Všetky ostatné uzly potom sú listové uzly, a preto nie je potrebné ich heapifikovať.
Môžeme teda vytvoriť maximálnu hromadu ako
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Vytvorte pole a vypočítajte i 
Kroky na vytvorenie maximálnej haldy na triedenie haldy 
Kroky na vybudovanie maximálnej haldy na triedenie haldy 
Kroky na vytvorenie maximálnej haldy na triedenie haldy
Ako je znázornené na vyššie uvedenom diagrame, začneme hromadením najnižších najmenších stromov a postupným pohybom nahor, kým nedosiahneme koreňový prvok.
Ak ste všetkému doteraz porozumeli, gratulujeme, ste na ceste k zvládnutiu haldy.
Ako funguje triedenie haldy?
- Pretože strom vyhovuje vlastnosti Max-Heap, potom je najväčšia položka uložená v koreňovom uzle.
- Swap: Odstráňte koreňový prvok a vložte ho na koniec poľa (n-tá pozícia). Na voľné miesto vložte poslednú položku stromu (halda).
- Odstrániť: Znížte veľkosť haldy o 1.
- Heapify: Heapify root element znova, takže máme najvyšší element v root.
- Proces sa opakuje, kým nie sú zoradené všetky položky v zozname.
Zamieňajte, odstraňujte a heapifikujte
Nasledujúci kód zobrazuje činnosť.
// 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); )
Príklady jazyka Python, Java a 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); )
Zložitosť triedenia haldy
Heap Sort má O(nlog n)časovú zložitosť pre všetky prípady (najlepší prípad, priemerný prípad a najhorší prípad).
Poďme pochopiť dôvod, prečo. Výška úplného binárneho stromu obsahujúceho n prvkov jelog n
Ako sme už videli skôr, aby sme úplne heapifikovali prvok, ktorého podstromy sú už max. Hromady, musíme neustále porovnávať prvok s jeho ľavými a pravými deťmi a tlačiť ho smerom nadol, kým nedosiahne bod, v ktorom sú obidve jeho deti menšie ako on.
V najhoršom prípade budeme musieť presunúť prvok z koreňa do listového uzla a vykonať tak log(n)porovnanie a zámenu.
Počas fázy build_max_heap to robíme pre n/2prvky, takže najhoršia zložitosť kroku build_heap je n/2*log n ~ nlog n.
Počas kroku triedenia vymeníme koreňový prvok za posledný a heapifikujeme koreňový prvok. Pre každý prvok to opäť trvá log nnajhoršie, pretože by sme možno museli prvok preniesť úplne od koreňa k listu. Pretože to opakujeme n-krát, je aj krok heap_sort nlog n.
Pretože sa kroky build_max_heapa heap_sortuskutočňujú jeden za druhým, algoritmická zložitosť sa neznásobuje a zostáva v poradí nlog n.
Vykonáva tiež triedenie v O(1)zložitosti priestoru. V porovnaní s rýchlym radením má lepší najhorší prípad ( O(nlog n) ). Rýchle triedenie má O(n^2)v najhoršom prípade zložitosť . V iných prípadoch je však rýchle triedenie rýchle. Introsort je alternatívou k heapsortu, ktorý kombinuje quicksort a heapsort, aby si zachoval výhody oboch: najhoršia rýchlosť heapsortu a priemerná rýchlosť quicksortu.
Aplikácie na triedenie haldy
Systémy zaoberajúce sa bezpečnosťou a vstavanými systémami, ako je Linux Kernel, používajú Heap Sort kvôli O(n log n)hornej hranici prevádzkovej doby Heapsortu a stálej O(1)hornej hranici svojej pomocnej pamäte.
Aj keď má triedenie hromady O(n log n)časovú zložitosť aj v najhoršom prípade, nemá viac aplikácií (v porovnaní s inými algoritmami triedenia ako Quick Sort, Merge Sort). Jej podkladová dátová štruktúra, halda, sa však dá efektívne využiť, ak chceme zo zoznamu položiek extrahovať najmenšie (alebo najväčšie) bez toho, aby sme zvyšné položky udržiavali v zoradenom poradí. Napríklad napr. Prioritné fronty.
