V tomto kurzu se dozvíte, jak funguje algoritmus řazení haldy. Také najdete pracovní příklady třídění haldy v C, C ++, Java a Python.
Heap Sort je populární a efektivní třídicí algoritmus v počítačovém programování. Naučit se psát algoritmus třídění haldy vyžaduje znalost dvou typů datových struktur - polí a stromů.
Počáteční sada čísel, která chceme třídit, je uložena v poli např. (10, 3, 76, 34, 23, 32)A po seřazení dostaneme seřazené pole(3,10,23,32,34,76)
Třídění haldy funguje tak, že vizualizuje prvky pole jako speciální druh úplného binárního stromu nazývaného halda.
Předpokladem je, že musíte vědět o úplném binárním stromu a struktuře dat haldy.
Vztah mezi indexy polí a prvky stromů
Kompletní binární strom má zajímavou vlastnost, kterou můžeme použít k vyhledání dětí a rodičů libovolného uzlu.
Pokud je index libovolného prvku v poli i, prvek v indexu 2i+1se stane levým potomkem a prvek v 2i+2indexu se stane pravým potomkem. Nadřazený prvek libovolného prvku v indexu i je dán dolní mezí (i-1)/2.
Vztah mezi indexy pole a haldy
Pojďme to vyzkoušet
Levé dítě 1 (index 0) = prvek v (2 * 0 + 1) index = prvek v 1 index = 12 Pravé dítě 1 = prvek v (2 * 0 + 2) index = prvek v 2 index = 9 Podobně Levé dítě 12 (index 1) = prvek v (2 * 1 + 1) index = prvek ve 3 index = 5 Pravé dítě 12 = prvek v (2 * 1 + 2) index = prvek ve 4 index = 6
Potvrďte také, že pravidla platí pro nalezení rodiče kteréhokoli uzlu
Rodič 9 (pozice 2) = (2-1) / 2 = ½ = 0,5 ~ 0 index = 1 Rodič 12 (pozice 1) = (1-1) / 2 = 0 index = 1
Pochopení tohoto mapování indexů pole na pozice stromů je zásadní pro pochopení toho, jak funguje halda datová struktura a jak se používá k implementaci třídění haldy.
Co je halda datová struktura?
Halda je speciální stromová datová struktura. O binárním stromu se říká, že sleduje strukturu dat haldy, pokud
- je to kompletní binární strom
- Všechny uzly ve stromu sledují vlastnost, že jsou větší než jejich podřízené, tj. Největší prvek je v kořenu a jeho podřízených a menší než kořen atd. Takové hromadě se říká maximální hromada. Pokud jsou místo toho všechny uzly menší než jejich děti, nazývá se to halda min
Následující ukázkový diagram ukazuje Max-Heap a Min-Heap.
Max. Halda a min. Halda
Chcete-li se dozvědět více, navštivte Heap Data Structure.
Jak "heapify" strom
Počínaje úplným binárním stromem jej můžeme upravit tak, aby se stal Max-Heap spuštěním funkce zvané heapify na všech nelistových prvcích haldy.
Protože heapify používá rekurzi, může být obtížné jej uchopit. Pojďme se tedy nejprve zamyslet nad tím, jak byste heapifikovali strom pouze se třemi prvky.
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í případy
Výše uvedený příklad ukazuje dva scénáře - jeden, ve kterém je root největší prvek a nemusíme nic dělat. A další, ve kterém měl kořen jako dítě větší prvek a my jsme potřebovali vyměnit, abychom udrželi vlastnost max-heap.
Pokud jste dříve pracovali s rekurzivními algoritmy, pravděpodobně jste zjistili, že to musí být základní případ.
Pojďme si představit další scénář, ve kterém existuje více než jedna úroveň.
Jak heapify root element, když jeho podstromy jsou již maximální hromady
Horní prvek není maximální hromada, ale všechny dílčí stromy jsou maximální hromady.
Abychom zachovali vlastnost max-heap pro celý strom, budeme muset neustále tlačit 2 dolů, dokud nedosáhne správné polohy.
Jak heapify kořenový prvek, když jeho podstromy jsou maximální hromady
Abychom tedy udrželi vlastnost max-heap ve stromu, kde jsou oba dílčí stromy max-haldy, musíme opakovaně spouštět heapify na kořenovém prvku, dokud nebude větší než jeho podřízené prvky nebo se nestane uzlem listu.
Můžeme kombinovat obě tyto podmínky v jedné funkci heapify 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); ) )
Tato funkce funguje jak pro základní případ, tak pro strom libovolné velikosti. Můžeme tedy přesunout kořenový prvek do správné polohy, abychom udrželi stav maximální haldy pro libovolnou velikost stromu, pokud jsou dílčí stromy maximální hromady.
Vybudujte maximální hromadu
Abychom vytvořili maximální hromadu z libovolného stromu, můžeme tedy začít heapifikovat každý dílčí strom zdola nahoru a skončit s maximální hromadou po aplikaci funkce na všechny prvky včetně kořenového prvku.
V případě úplného stromu je první index nelistového uzlu dán vztahem n/2 - 1. Všechny ostatní uzly po tom jsou uzly listů, a proto nemusí být heapifikovány.
Můžeme tedy vytvořit maximální hromadu jako
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Vytvoření pole a výpočet i 
Kroky k vytvoření maximální haldy pro třídění haldy 
Kroky k vytvoření maximální haldy pro třídění haldy 
Kroky k vytvoření maximální haldy pro třídění haldy
Jak ukazuje výše uvedený diagram, začneme hromaděním nejmenších nejmenších stromů a postupně se pohybujeme nahoru, dokud nedosáhneme kořenového prvku.
Pokud jste všemu porozuměli až dosud, gratulujeme, jste na cestě k osvojení typu haldy.
Jak funguje třídění haldy?
- Vzhledem k tomu, že strom splňuje vlastnost Max-Heap, je největší položka uložena v kořenovém uzlu.
- Swap: Odeberte kořenový prvek a vložte jej na konec pole (n-ta pozice). Umístěte poslední položku stromu (haldu) na volné místo.
- Odstranit: Zmenšete velikost haldy o 1.
- Heapify: Heapify kořenový prvek znovu, takže máme nejvyšší prvek v kořenovém adresáři.
- Proces se opakuje, dokud nejsou seřazeny všechny položky seznamu.
Zaměnit, odebrat a Heapify
Níže uvedený kód ukazuje operaci.
// 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 a C / C ++ příklady
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); )
Složitost řazení haldy
Heap Sort má O(nlog n)časovou složitost pro všechny případy (nejlepší případ, průměrný případ a nejhorší případ).
Pochopme důvod, proč. Výška úplného binárního stromu obsahujícího n prvků jelog 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.
Ačkoli Heap Sort má O(n log n)časovou složitost i v nejhorším případě, nemá více aplikací (ve srovnání s jinými třídicími algoritmy jako Quick Sort, Merge Sort). Jeho základní datová struktura, halda, však může být efektivně použita, pokud chceme extrahovat nejmenší (nebo největší) ze seznamu položek bez režie udržování zbývajících položek v seřazeném pořadí. Např. Prioritní fronty.
