heap sort c with examples
En introduksjon til haugsortering med eksempler.
Heapsort er en av de mest effektive sorteringsteknikkene. Denne teknikken bygger en haug fra den gitte usorterte matrisen og bruker deretter haugen igjen for å sortere matrisen.
Heapsort er en sorteringsteknikk basert på sammenligning og bruker binær heap.
=> Les gjennom Easy C ++ Training Series.
hvordan du installerer .bin-filen
Hva du vil lære:
- Hva er en binær haug?
- Generell algoritme
- Illustrasjon
- C ++ Eksempel
- Java-eksempel
- Konklusjon
- Anbefalt lesing
Hva er en binær haug?
En binær haug er representert ved hjelp av et komplett binært tre. Et komplett binært tre er et binært tre der alle nodene på hvert nivå er fullstendig fylt bortsett fra bladnodene og nodene er så langt som til venstre.
En binær haug eller bare en haug er et komplett binært tre der elementene eller nodene er lagret på en slik måte at rotnoden er større enn de to undernodene. Dette kalles også max heap.
Elementene i den binære bunken kan også lagres som min-heap der rotnoden er mindre enn de to undernodene. Vi kan representere en haug som et binært tre eller en matrise.
Mens du representerer en haug som en matrise, forutsatt at indeksen starter ved 0, lagres rotelementet ved 0. Generelt sett, hvis en foreldrenode er i posisjon I, så er den venstre barnekoden i posisjonen (2 * I + 1) og høyre node er ved (2 * I +2).
Generell algoritme
Nedenfor er den generelle algoritmen for haugsorteringsteknikk.
- Bygg en maks haug fra de gitte dataene slik at roten er det høyeste elementet i haugen.
- Fjern roten, dvs. det høyeste elementet fra dyngen, og bytt ut eller bytt den med det siste elementet i dyngen.
- Juster deretter maks heap for ikke å bryte maks heap egenskaper (heapify).
- Ovennevnte trinn reduserer haugestørrelsen med 1.
- Gjenta de ovennevnte tre trinnene til dyngestørrelsen er redusert til 1.
Som vist i den generelle algoritmen for å sortere det gitte datasettet i økende rekkefølge, konstruerer vi først en maks bunke for de gitte dataene.
La oss ta et eksempel for å konstruere en maksimal heap med følgende datasett.
6, 10, 2, 4, 1
Vi kan konstruere et tre for dette datasettet som følger.
I ovenstående trerepresentasjon representerer tallene i parentes de respektive posisjonene i matrisen.
For å konstruere en maksimal dyng av ovennevnte representasjon, må vi oppfylle bunkevilkåret om at foreldrenoden skal være større enn sine undernoder. Med andre ord, vi trenger å 'heapify' treet for å konvertere det til max-heap.
Etter heapification av treet ovenfor, får vi maks-heap som vist nedenfor.
Som vist ovenfor har vi denne maksimale bunken generert fra en matrise.
Deretter presenterer vi en illustrasjon av en haugsort. Etter å ha sett konstruksjonen av max-heap, hopper vi over de detaljerte trinnene for å konstruere en max-heap og viser direkte maks heap ved hvert trinn.
Illustrasjon
Tenk på følgende utvalg av elementer. Vi må sortere denne matrisen ved hjelp av heap sort-teknikken.
La oss konstruere en maks-heap som vist nedenfor for matrisen som skal sorteres.
Når haugen er konstruert, representerer vi den i en matriseform som vist nedenfor.
Nå sammenligner vi 1St.node (root) med den siste noden og bytt dem deretter. Således, som vist ovenfor, bytter vi 17 og 3 slik at 17 er i siste posisjon og 3 er i første posisjon.
Nå fjerner vi noden 17 fra dyngen og legger den i den sorterte matrisen som vist i den skyggelagte delen nedenfor.
Nå konstruerer vi igjen en haug for matriseelementene. Denne gangen blir hopestørrelsen redusert med 1 ettersom vi har slettet ett element (17) fra haugen.
Haugen av de gjenværende elementene er vist nedenfor.
I neste trinn vil vi gjenta de samme trinnene.
Vi sammenligner og bytter rotelementet og det siste elementet i dyngen.
Etter bytte sletter vi elementet 12 fra haugen og flytter det til den sorterte matrisen.
Nok en gang konstruerer vi en maks bunke for de gjenværende elementene som vist nedenfor.
Nå bytter vi roten og det siste elementet, dvs. 9 og 3. Etter bytte slettes element 9 fra haugen og settes i en sortert matrise.
På dette punktet har vi bare tre elementer i dyngen som vist nedenfor.
"standard gateway er ikke tilgjengelig"
Vi bytter 6 og 3 og sletter elementet 6 fra dyngen og legger det til den sorterte matrisen.
Nå konstruerer vi en haug av de gjenværende elementene og bytter begge ut med hverandre.
Etter å ha byttet 4 og 3, sletter vi element 4 fra dyngen og legger det til den sorterte matrisen. Nå har vi bare en node igjen i haugen som vist nedenfor .
Så nå med bare én node igjen, sletter vi den fra haugen og legger den til i den sorterte matrisen.
Jeg trenger en ny e-postleverandør
Dermed er ovennevnte den sorterte matrisen som vi har oppnådd som et resultat av haugsorteringen.
I illustrasjonen ovenfor har vi sortert matrisen i stigende rekkefølge. Hvis vi må sortere matrisen i synkende rekkefølge, må vi følge de samme trinnene, men med min-haugen.
Heapsort-algoritme er identisk med utvalgssortering der vi velger det minste elementet og plasserer det i en sortert matrise. Haugsortering er imidlertid raskere enn utvalgssortering når det gjelder ytelsen. Vi kan si det som heapsort er en forbedret versjon av sortimentet.
Deretter vil vi implementere Heapsort på C ++ og Java-språk.
Den viktigste funksjonen i begge implementeringene er funksjonen “heapify”. Denne funksjonen kalles av den viktigste heapsort-rutinen for å omorganisere undertreet når en node er slettet eller når max-heap er bygget.
Når vi har heapet treet riktig, bare da vil vi kunne få de riktige elementene i riktig posisjon, og dermed blir matrisen riktig sortert.
C ++ Eksempel
Følgende er C ++ - koden for implementering av heapsort.
#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 Produksjon:
Inndata matrise
4 17 3 12 9 6
Sortert utvalg
3 4 6 9 12 17
Deretter vil vi implementere heapsort på Java-språk
Java-eksempel
// 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 Produksjon:
Inndata matrise:
4 17 3 12 9 6
Sortert utvalg:
3 4 6 9 12 17
Konklusjon
Heapsort er en sammenligningsbasert sorteringsteknikk ved hjelp av binær heap.
Det kan betegnes som en forbedring i forhold til utvalgssortering, siden begge disse sorteringsteknikkene fungerer med lignende logikk for å finne det største eller minste elementet i matrisen gjentatte ganger og deretter plassere den i den sorterte matrisen.
Heap sort bruker maks-heap eller min-heap for å sortere matrisen. Det første trinnet i haugsortering er å bygge en min eller maks haug fra matrisedataene, og deretter slette rotelementet rekursivt og heapify haugen til det bare er en node tilstede i haugen.
Heapsort er en effektiv algoritme og fungerer raskere enn utvalgssortering. Den kan brukes til å sortere en nesten sortert matrise eller finne k største eller minste element i matrisen.
Med dette har vi fullført temaet vårt om sorteringsteknikker i C ++. Fra vår neste opplæring og utover, vil vi starte med datastrukturer en etter en.
=> Se etter hele C ++ treningsserien her.
Anbefalt lesing
- MongoDB Sort () Metode med eksempler
- Unix sorteringskommando med syntaks, alternativer og eksempler
- Flett sortering i C ++ med eksempler
- Skalsortering i C ++ med eksempler
- Innsettingssortering i C ++ med eksempler
- Valgsortering i C ++ med eksempler
- Boblesortering i C ++ med eksempler
- Rask sortering i C ++ med eksempler