heap sort c with examples
Úvod do hromadného triedenia s príkladmi.
Heapsort je jednou z najefektívnejších triediacich techník. Táto technika vytvorí hromadu z daného netriedeného poľa a potom ju použije na ďalšie zoradenie poľa.
Heapsort je technika triedenia založená na porovnaní a využíva binárnu haldu.
=> Prečítajte si sériu školení Easy C ++.
príklad pre abstraktné rozhranie v jave
Čo sa dozviete:
- Čo je to binárna halda?
- Všeobecný algoritmus
- Ilustrácia
- Príklad C ++
- Príklad Java
- Záver
- Odporúčané čítanie
Čo je to binárna halda?
Binárna halda je znázornená pomocou úplného binárneho stromu. Kompletný binárny strom je binárny strom, v ktorom sú všetky uzly na každej úrovni úplne vyplnené, s výnimkou listových uzlov a uzlov úplne zľava.
Binárna halda alebo jednoducho halda je úplný binárny strom, kde sú položky alebo uzly uložené takým spôsobom, že koreňový uzol je väčší ako jeho dva podradené uzly. Toto sa tiež nazýva max halda.
Položky v binárnej halde možno tiež uložiť ako minimálnu haldu, v ktorej je koreňový uzol menší ako jeho dva podradené uzly. Hromadu môžeme reprezentovať ako binárny strom alebo pole.
Keď predstavuje hromadu ako pole, za predpokladu, že index začína na 0, koreňový prvok je uložený na 0. Všeobecne platí, že ak je nadradený uzol na pozícii I, potom je ľavý podradený uzol na pozícii (2 * I + 1) a pravý uzol je na (2 * I +2).
Všeobecný algoritmus
Ďalej je uvedený všeobecný algoritmus pre techniku triedenia haldy.
- Z daných údajov vytvorte maximálnu hromadu tak, aby root bol najvyšším prvkom haldy.
- Odstráňte koreň, tj. Najvyšší prvok z haldy, a nahraďte ho alebo vymeňte za posledný element z haldy.
- Potom upravte maximálnu haldu tak, aby nedošlo k porušeniu maximálnych vlastností haldy (heapify).
- Vyššie uvedený krok zmenší veľkosť haldy o 1.
- Opakujte vyššie uvedené tri kroky, kým sa veľkosť haldy nezníži na 1.
Ako je znázornené vo všeobecnom algoritme na triedenie danej množiny údajov v narastajúcom poradí, najskôr pre dané údaje zostrojíme maximálnu hromadu.
Zoberme si príklad na zostrojenie maximálnej haldy s nasledujúcou množinou údajov.
6, 10, 2, 4, 1
Pre túto množinu údajov môžeme skonštruovať strom nasledovne.
Vo vyššie uvedenom stromovom zastúpení predstavujú čísla v zátvorkách príslušné pozície v poli.
Aby sme vytvorili maximálnu hromadu vyššie uvedenej reprezentácie, musíme splniť podmienku haldy, že nadradený uzol by mal byť väčší ako jeho podradené uzly. Inými slovami, musíme strom „heapifikovať“, aby sme ho mohli previesť na max-heap.
Po heapifikácii vyššie uvedeného stromu dostaneme maximálnu hromadu, ako je znázornené nižšie.
Ako je uvedené vyššie, máme túto maximálnu hromadu vygenerovanú z poľa.
Ďalej uvádzame ilustráciu typu haldy. Keď sme videli konštrukciu max-haldy, preskočíme podrobné kroky na zostavenie max-haldy a priamo ukážeme maximálnu haldu v každom kroku.
Ilustrácia
Zvážte nasledujúce pole prvkov. Musíme zoradiť toto pole pomocou techniky triedenia haldy.
Vytvorme maximálnu hromadu, ako je znázornené nižšie, pre pole, ktoré sa má zoradiť.
Keď je hromada skonštruovaná, predstavujeme ju v podobe poľa, ako je to znázornené nižšie.
Teraz porovnáme 1svuzol (root) s posledným uzlom a potom ich vymeniť. Ako je to znázornené vyššie, zamieňame 17 a 3 tak, aby 17 bolo na poslednej pozícii a 3 na prvej pozícii.
Teraz odstránime uzol 17 z haldy a vložíme ho do zoradeného poľa, ako je znázornené v tieňovanej časti nižšie.
Teraz opäť zostrojíme haldu pre prvky poľa. Tentokrát sa veľkosť haldy zníži o 1, pretože sme z haldy odstránili jeden prvok (17).
Hromada zvyšných prvkov je uvedená nižšie.
V ďalšom kroku zopakujeme rovnaké kroky.
Porovnáme a zameníme koreňový a posledný prvok v halde.
Po výmene vymažeme prvok 12 z haldy a presunieme ho do zoradeného poľa.
Opäť zostrojíme maximálnu hromadu pre zvyšné prvky, ako je to znázornené nižšie.
Teraz zameníme koreň a posledný prvok, tj. 9 a 3. Po výmene je prvok 9 z haldy odstránený a vložený do zoradeného poľa.
najlepší telefónny špiónsky softvér pre Android
V tomto okamihu máme v kope iba tri prvky, ako je to znázornené nižšie.
Zameníme 6 a 3 a odstránime prvok 6 z haldy a pridáme ho do zoradeného poľa.
Teraz zostrojíme kopu zostávajúcich prvkov a potom ich navzájom zameníme.
Po výmene 4 a 3 odstránime z haldy prvok 4 a pridáme ho do zoradeného poľa. Teraz nám na halde zostáva iba jeden uzol, ako je to znázornené nižšie .
Takže teraz, keď už zostáva iba jeden uzol, odstránime ho z haldy a pridáme do zoradeného poľa.
Vyššie uvedené je teda zoradené pole, ktoré sme získali ako výsledok haldy.
Na vyššie uvedenej ilustrácii sme zoradili pole vo vzostupnom poradí. Ak musíme zoradiť pole v zostupnom poradí, musíme postupovať rovnako, ale s minimálnou hromadou.
Heapsortov algoritmus je identický s výberovým triedením, pri ktorom vyberieme najmenší prvok a umiestnime ho do zoradeného poľa. Z hľadiska výkonu je však triedenie haldy rýchlejšie ako výberové. Môžeme to povedať, pretože heapsort je vylepšená verzia druhu výberu.
Ďalej implementujeme Heapsort v jazykoch C ++ a Java.
Najdôležitejšou funkciou v oboch implementáciách je funkcia „heapify“. Táto funkcia je volaná hlavnou rutinou heapsortu na preusporiadanie podstromu po odstránení uzla alebo po vytvorení max-heap.
Keď strom správne heapifikujeme, až potom budeme môcť získať správne prvky na ich správne pozície a pole bude teda správne zoradené.
Príklad C ++
Nasleduje kód C ++ pre implementáciu haldy.
#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ýkon:
Vstupné pole
4 17 3 12 9 6
Zoradené pole
3 4 6 9 12 17
Ďalej implementujeme heapsort v jazyku Java
Prí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ýkon:
Vstupné pole:
4 17 3 12 9 6
Zoradené pole:
3 4 6 9 12 17
Záver
Heapsort je technika triedenia založená na porovnaní využívajúca binárnu haldu.
Dá sa to nazvať ako vylepšenie výberu podľa triedenia, pretože obe tieto techniky triedenia pracujú s podobnou logikou opakovaného hľadania najväčšieho alebo najmenšieho prvku v poli a jeho následného umiestnenia do zoradeného poľa.
Hromadné triedenie využíva na triedenie poľa max-haldy alebo min-haldy. Prvým krokom pri triedení haldy je zostavenie minimálnej alebo maximálnej haldy z údajov poľa a potom rekurzívne odstránenie koreňového prvku a haldy haldy, kým v halde nebude iba jeden uzol.
Heapsort je efektívny algoritmus, ktorý pracuje rýchlejšie ako výberové triedenie. Môže sa použiť na triedenie takmer zoradeného poľa alebo na vyhľadanie k najväčších alebo najmenších prvkov v poli.
otázky a odpovede týkajúce sa kontroly kvality pdf
Týmto sme dokončili našu tému o technikách triedenia v C ++. Od nášho ďalšieho tutoriálu začneme postupne s dátovými štruktúrami.
=> Celú sériu školení pre C ++ nájdete tu.
Odporúčané čítanie
- Metóda MongoDB Sort () s príkladmi
- Unixový príkaz na triedenie so syntaxou, možnosťami a príkladmi
- Zlúčiť zoradenie v C ++ s príkladmi
- Shell zoradený v C ++ s príkladmi
- Zoradenie vloženia v C ++ s príkladmi
- Výber Zoradiť v C ++ s príkladmi
- Bublinové triedenie v C ++ s príkladmi
- Rýchle triedenie v C ++ s príkladmi