heap sort c with examples
Úvod do hromadného třídění s příklady.
Heapsort je jednou z nejúčinnějších třídicích technik. Tato technika vytvoří hromadu z daného netříděného pole a poté pomocí hromady znovu seřadí pole.
Heapsort je technika třídění založená na porovnání a využívá binární haldy.
=> Přečtěte si sérii školení Easy C ++.
fig_cropper.swf jak se otevřít
Co se naučíte:
- Co je to binární halda?
- Obecný algoritmus
- Ilustrace
- Příklad C ++
- Příklad Java
- Závěr
- Doporučené čtení
Co je to binární halda?
Binární halda je reprezentována pomocí úplného binárního stromu. Kompletní binární strom je binární strom, ve kterém jsou všechny uzly na každé úrovni zcela vyplněny, s výjimkou listových uzlů a uzly jsou zcela vlevo.
Binární halda nebo jednoduše halda je úplný binární strom, kde jsou položky nebo uzly uloženy takovým způsobem, že kořenový uzel je větší než jeho dva podřízené uzly. Tomu se také říká maximální halda.
Položky v binární haldě lze také uložit jako minimální haldu, kde je kořenový uzel menší než jeho dva podřízené uzly. Hromadu můžeme představovat jako binární strom nebo pole.
Zatímco představuje hromadu jako pole, za předpokladu, že index začíná na 0, je kořenový prvek uložen na 0. Obecně platí, že pokud je nadřazený uzel na pozici I, pak je levý podřízený uzel na pozici (2 * I + 1) a pravý uzel je na (2 * I +2).
Obecný algoritmus
Níže je uveden obecný algoritmus pro třídění haldy.
- Vytvořte maximální hromadu z daných dat tak, aby byl kořen nejvyšším prvkem haldy.
- Odstraňte kořen, tj. Nejvyšší prvek z haldy, a nahraďte jej nebo vyměňte za poslední prvek haldy.
- Poté upravte maximální hromadu, aby nedošlo k porušení maximálních vlastností haldy (heapify).
- Výše uvedený krok zmenší velikost haldy o 1.
- Opakujte výše uvedené tři kroky, dokud se velikost haldy nezmenší na 1.
Jak je znázorněno v obecném algoritmu pro seřazení dané datové sady ve vzestupném pořadí, nejprve vytvoříme pro dané údaje maximální hromadu.
Vezměme si příklad pro konstrukci maximální haldy s následující datovou sadou.
6, 10, 2, 4, 1
Pro tuto datovou sadu můžeme postavit strom následujícím způsobem.
Ve výše uvedené stromové reprezentaci představují čísla v závorkách příslušné pozice v poli.
Aby bylo možné vytvořit maximální hromadu výše uvedené reprezentace, musíme splnit podmínku haldy, že nadřazený uzel by měl být větší než jeho podřízené uzly. Jinými slovy, musíme strom „heapifikovat“, abychom jej převedli na max-heap.
Po heapifikaci výše uvedeného stromu získáme maximální hromadu, jak je znázorněno níže.
Jak je uvedeno výše, máme tuto maximální hromadu vygenerovanou z pole.
Dále představíme ilustraci typu haldy. Když jsme viděli konstrukci max-haldy, přeskočíme podrobné kroky pro konstrukci max-haldy a přímo ukážeme maximální haldu v každém kroku.
Ilustrace
Zvažte následující pole prvků. Musíme toto pole seřadit pomocí techniky třídění haldy.
Postavme maximální hromadu, jak je znázorněno níže, pro pole, které má být tříděno.
Jakmile je hromada zkonstruována, představujeme ji ve formě pole, jak je znázorněno níže.
Nyní porovnáme 1Svatýuzel (root) s posledním uzlem a poté je vyměnit. Jak je tedy ukázáno výše, zaměňujeme 17 a 3, takže 17 je na poslední pozici a 3 je na první pozici.
Nyní odstraníme uzel 17 z haldy a umístíme jej do seřazeného pole, jak je znázorněno ve stínované části níže.
Nyní znovu sestavíme hromadu prvků pole. Tentokrát je velikost haldy snížena o 1, protože jsme z haldy odstranili jeden prvek (17).
Hromada zbývajících prvků je uvedena níže.
V dalším kroku zopakujeme stejné kroky.
Porovnáme a vyměníme kořenový prvek a poslední prvek v haldě.
Po výměně odstraníme prvek 12 z haldy a přesuneme jej do seřazeného pole.
Opět vytvoříme maximální hromadu pro zbývající prvky, jak je znázorněno níže.
Nyní vyměníme kořen a poslední prvek, tj. 9 a 3. Po výměně je prvek 9 odstraněn z haldy a vložen do tříděného pole.
V tomto okamžiku máme v haldě pouze tři prvky, jak je znázorněno níže.
Zaměníme 6 a 3 a odstraníme prvek 6 z haldy a přidáme jej do seřazeného pole.
otázky a odpovědi na rozhovor o testování softwaru
Nyní zkonstruujeme hromadu zbývajících prvků a potom je vyměníme navzájem.
Po výměně 4 a 3 odstraníme prvek 4 z haldy a přidáme jej do seřazeného pole. Nyní nám v haldě zbývá pouze jeden uzel, jak je znázorněno níže .
Nyní tedy zbývá pouze jeden uzel, odstraníme jej z haldy a přidáme do tříděného pole.
Výše uvedené je tedy seřazené pole, které jsme získali jako výsledek haldy.
Na výše uvedeném obrázku jsme pole setřídili vzestupně. Pokud musíme řadit pole v sestupném pořadí, musíme postupovat podle stejných kroků, ale s minimální hromadou.
Heapsortův algoritmus je identický s výběrem řazení, ve kterém vybereme nejmenší prvek a umístíme jej do seřazeného pole. Hromadné řazení je však rychlejší než výběrové, pokud jde o výkon. Můžeme to vyjádřit, protože heapsort je vylepšená verze druhu výběru.
Dále implementujeme Heapsort v jazyce C ++ a Java.
implementace hash tabulky c ++
Nejdůležitější funkcí v obou implementacích je funkce „heapify“. Tato funkce je volána hlavní rutinou heapsortu k přeskupení podstromu, jakmile je uzel odstraněn nebo když je vytvořena max-heap.
Když jsme strom správně heapifikovali, teprve potom budeme moci získat správné prvky do jejich správných pozic a pole bude tedy správně tříděno.
Příklad C ++
Následuje kód C ++ pro implementaci heapsortu.
#include using namespace std; // function to heapify the tree void heapify(int arr(), int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr(root), arr(largest)); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr(), int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr(0), arr(i)); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr(), int n) { for (int i=0; i Výstup:
Vstupní pole
4 17 3 12 9 6
Seřazené pole
3 4 6 9 12 17
Dále implementujeme heapsort v jazyce Java
Příklad Java
// Java program to implement Heap Sort class HeapSort { public void heap_sort(int arr()) { int n = arr.length; // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for (int i=n-1; i>=0; i--) { // Move current root to end int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // call max heapify on the reduced heap heapify(arr, i, 0); } } // heapify the sub-tree void heapify(int arr(), int n, int root) { int largest = root; // Initialize largest as root int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { int swap = arr(root); arr(root) = arr(largest); arr(largest) = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } //print array contents - utility function static void displayArray(int arr()) { int n = arr.length; for (int i=0; i Výstup:
Vstupní pole:
4 17 3 12 9 6
Seřazené pole:
3 4 6 9 12 17
Závěr
Heapsort je technika třídění založená na komparaci využívající binární haldy.
Lze jej označit jako vylepšení oproti výběru řazení, protože obě tyto techniky řazení pracují s podobnou logikou opakovaného hledání největšího nebo nejmenšího prvku v poli a jeho následného umístění do seřazeného pole.
Třídění haldy využívá k seřazení pole max. Haldy nebo min. Haldy. Prvním krokem při třídění haldy je sestavení min nebo max haldy z dat pole a poté rekurzivně odstranit kořenový prvek a heapify haldy, dokud v haldě není pouze jeden uzel.
Heapsort je efektivní algoritmus a funguje rychleji než výběrové třídění. Může být použit k třídění téměř seřazeného pole nebo k vyhledání k největších nebo nejmenších prvků v poli.
Tím jsme dokončili naše téma o technikách řazení v C ++. Od našeho dalšího tutoriálu začneme postupně s datovými strukturami.
=> Podívejte se na celou sérii školení C ++ zde.
Doporučené čtení