heap sort c with examples
Uvod u sortiranje hrpe s primjerima.
Heapsort je jedna od najučinkovitijih tehnika sortiranja. Ova tehnika gradi hrpu od datog nesortiranog niza, a zatim ponovno koristi hrpu za sortiranje niza.
Heapsort je tehnika sortiranja koja se temelji na usporedbi i koristi binarnu hrpu.
=> Pročitajte seriju Easy C ++ Training Series.
kako koristiti Java za otvaranje jar datoteke
Što ćete naučiti:
- Što je binarna hrpa?
- Opći algoritam
- Ilustracija
- Primjer C ++
- Primjer Java
- Zaključak
- Preporučena literatura
Što je binarna hrpa?
Binarna hrpa predstavljena je pomoću cjelovitog binarnog stabla. Potpuno binarno stablo je binarno stablo u kojem su svi čvorovi na svakoj razini u potpunosti popunjeni, osim čvorova listova i čvorovi su do lijeve strane.
Binarna hrpa ili jednostavno hrpa cjelovito je binarno stablo u kojem su stavke ili čvorovi pohranjeni na način da je korijenski čvor veći od svoja dva podređena čvora. To se također naziva max hrpa.
Stavke u binarnoj hrpi također se mogu pohraniti kao min-heap gdje je korijenski čvor manji od svoja dva podređena čvora. Hrpu možemo predstaviti kao binarno stablo ili niz.
Dok predstavlja hrpu kao niz, pod pretpostavkom da indeks započinje s 0, korijenski se element pohranjuje na 0. Općenito, ako je nadređeni čvor na položaju I, tada je lijevi podređeni čvor na položaju (2 * I + 1) i desni čvor je na (2 * I +2).
Opći algoritam
Slijedi opći algoritam za tehniku sortiranja hrpe.
- Napravite maksimalnu hrpu od zadanih podataka tako da je korijen najviši element hrpe.
- Uklonite korijen tj. Najviši element iz hrpe i zamijenite ga ili zamijenite posljednjim elementom hrpe.
- Zatim prilagodite maksimalnu hrpu kako ne bi kršili svojstva maksimalne hrpe (heapify).
- Gornji korak smanjuje veličinu hrpe za 1.
- Ponavljajte gornja tri koraka dok se veličina hrpe ne smanji na 1.
Kao što je prikazano u općem algoritmu za sortiranje datog skupa podataka u rastućem redoslijedu, prvo konstruiramo maksimalnu hrpu za dane podatke.
Uzmimo primjer za izgradnju maksimalne hrpe sa sljedećim skupom podataka.
6, 10, 2, 4, 1
Za ovaj skup podataka možemo konstruirati stablo na sljedeći način.
U gornjem prikazu stabla, brojevi u zagradama predstavljaju odgovarajuće položaje u polju.
Da bismo konstruirali maksimalnu hrpu gornjeg prikaza, moramo ispuniti uvjet hrpe da nadređeni čvor bude veći od njegovih podređenih čvorova. Drugim riječima, trebamo 'gomilati' drvo kako bismo ga pretvorili u max-heap.
Nakon gomilanja gornjeg stabla, dobit ćemo maksimalnu hrpu kako je prikazano dolje.
Kao što je gore prikazano, imamo ovu max-hrpu generiranu iz niza.
Dalje, predstavljamo ilustraciju vrste hrpe. Nakon što smo vidjeli konstrukciju max-heap-a, preskočit ćemo detaljne korake za izgradnju max-heap-a i izravno ćemo prikazati max-heap u svakom koraku.
Ilustracija
Razmotrite sljedeći niz elemenata. Moramo sortirati ovaj niz tehnikom sortiranja hrpe.
Izgradimo max-hrpu kako je prikazano dolje za niz koji će se sortirati.
Nakon što je hrpa izgrađena, predstavljamo je u obliku niza kao što je prikazano dolje.
Sada uspoređujemo 1svčvor (korijen) sa zadnjim čvorom, a zatim ih zamijenite. Dakle, kao što je gore prikazano, zamjenjujemo 17 i 3 tako da je 17 na posljednjem položaju, a 3 na prvom mjestu.
Sada uklanjamo čvor 17 iz gomile i stavljamo ga u razvrstani niz kako je prikazano u zasjenjenom dijelu ispod.
Sada opet konstruiramo hrpu za elemente niza. Ovaj put veličina hrpe smanjuje se za 1 jer smo iz hrpe izbrisali jedan element (17).
Gomila preostalih elemenata prikazana je u nastavku.
U sljedećem ćemo koraku ponoviti iste korake.
Usporedimo i zamijenimo korijenski element i zadnji element u hrpi.
kako otvoriti nešto s javom
Nakon zamjene, brišemo element 12 iz hrpe i premještamo ga u razvrstani niz.
Još jednom konstruiramo maksimalnu hrpu za preostale elemente kao što je prikazano dolje.
Sada zamijenimo korijen i posljednji element, tj. 9 i 3. Nakon zamjene, element 9 se briše iz hrpe i stavlja u razvrstani niz.
U ovom trenutku u hrpi imamo samo tri elementa kao što je prikazano u nastavku.
Zamijenimo 6 i 3 i izbrišemo element 6 iz gomile i dodamo ga u razvrstani niz.
Sada konstruiramo hrpu preostalih elemenata, a zatim ih međusobno zamijenimo.
Nakon zamjene 4 i 3, brišemo element 4 iz hrpe i dodamo ga u razvrstani niz. Sada imamo samo jedan čvor u hrpi kao što je prikazano dolje .
Dakle, sada kada je ostao samo jedan čvor, brišemo ga iz gomile i dodajemo u razvrstani niz.
Stoga je gore prikazano sortirani niz koji smo dobili kao rezultat sortiranja hrpe.
Na gornjoj ilustraciji sortirali smo niz u rastućem redoslijedu. Ako moramo sortirati niz silaznim redoslijedom, trebamo slijediti iste korake, ali s min-hrpom.
Algoritam Heapsort identičan je sortiranju odabira u kojem odabiremo najmanji element i smještamo ga u sortirani niz. Međutim, sortiranje hrpe brže je od sortiranja odabira što se tiče izvedbe. Možemo reći da je sorta gomile poboljšana verzija vrste odabira.
Dalje, implementirat ćemo Heapsort na C ++ i Java jezik.
Najvažnija funkcija u obje implementacije je funkcija 'heapify'. Ovu funkciju poziva glavna rutina sortiranja za preuređivanje podstabla kada se čvor izbriše ili kada se izgradi max-heap.
Kada smo stablo pravilno napuhali, tek tada ćemo moći dobiti ispravne elemente u odgovarajuće položaje i tako će niz biti pravilno sortiran.
Primjer C ++
Slijedi C ++ kôd za implementaciju protokola.
#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 Izlaz:
Ulazni niz
4 17 3 12 9 6
Sortirani niz
3 4 6 9 12 17
najbolji besplatni softver za poboljšanje performansi računala
Dalje, implementirat ćemo hepsort na Java jeziku
Primjer 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 Izlaz:
Ulazni niz:
4 17 3 12 9 6
Sortirani niz:
3 4 6 9 12 17
Zaključak
Heapsort je tehnika sortiranja temeljena na usporedbi pomoću binarne hrpe.
Može se nazvati poboljšanjem u odnosu na sortiranje odabira, jer obje ove tehnike sortiranja rade sa sličnom logikom ponovnog pronalaženja najvećeg ili najmanjeg elementa u nizu, a zatim ga stavljanja u sortirani niz.
Sortiranje hrpe koristi max-heap ili min-heap za sortiranje niza. Prvi korak u sortiranju hrpe je izgradnja minimalne ili maksimalne hrpe iz podataka niza, a zatim rekurzivno brisanje korijenskog elementa i gomilanje hrpe dok u hrpi ne postoji samo jedan čvor.
Heapsort je učinkovit algoritam i izvršava se brže od sortiranja odabira. Može se koristiti za sortiranje gotovo razvrstanog niza ili pronalaženje k najvećih ili najmanjih elemenata u nizu.
Ovim smo dovršili našu temu o tehnikama sortiranja na C ++. Od našeg sljedećeg vodiča nadalje, započet ćemo s podatkovnim strukturama jednu po jednu.
=> Ovdje potražite cijelu seriju treninga za C ++.
Preporučena literatura
- MongoDB metoda sortiranja () s primjerima
- Unix naredba za sortiranje sa sintaksom, opcijama i primjerima
- Spoji sortiranje u C ++ s primjerima
- Razvrstavanje ljuske na C ++ s primjerima
- Sortiranje umetanja u C ++ s primjerima
- Sortiranje odabira na C ++ s primjerima
- Razvrstavanje mjehurića na C ++ s primjerima
- Brzo sortiranje u C ++ s primjerima