heap sort c with examples
En introduktion till högsortering med exempel.
Heapsort är en av de mest effektiva sorteringsteknikerna. Denna teknik bygger en hög från den angivna osorterade matrisen och använder sedan högen igen för att sortera matrisen.
Heapsort är en sorteringsteknik baserad på jämförelse och använder binär hög.
=> Läs igenom Easy C ++ Training Series.
livscykel för utveckling av vattenfallsmodellsystem
Vad du kommer att lära dig:
- Vad är en binär hög?
- Allmän algoritm
- Illustration
- C ++ Exempel
- Java-exempel
- Slutsats
- Rekommenderad läsning
Vad är en binär hög?
En binär hög representeras med hjälp av ett komplett binärt träd. Ett komplett binärt träd är ett binärt träd där alla noder på varje nivå är helt fyllda förutom bladnoderna och noderna är så långt som vänster.
En binär hög eller helt enkelt en hög är ett komplett binärt träd där objekten eller noder lagras på ett sådant sätt att rotnoden är större än dess två undernoder. Detta kallas också max heap.
Objekten i den binära högen kan också lagras som min-hög, där rotnoden är mindre än de två undernoderna. Vi kan representera en hög som ett binärt träd eller en matris.
Samtidigt som en höjd representeras som en matris, förutsatt att indexet börjar vid 0, lagras rotelementet vid 0. Om en föräldernod är i position I är generellt den vänstra barnnoden i positionen (2 * I + 1) och höger nod är vid (2 * I +2).
Allmän algoritm
Nedan följer den allmänna algoritmen för högsorteringsteknik.
- Bygg en maxhög från den givna informationen så att roten är det högsta elementet i högen.
- Ta bort roten, dvs. det högsta elementet från högen och byt ut eller byt ut det med det sista elementet i högen.
- Justera sedan maxheap för att inte bryta mot maxheapegenskaperna (heapify).
- Ovanstående steg minskar högstorleken med 1.
- Upprepa ovanstående tre steg tills högstorleken minskas till 1.
Som visas i den allmänna algoritmen för att sortera den givna datasetet i ökande ordning, konstruerar vi först en maxhöjd för den givna datan.
Låt oss ta ett exempel för att konstruera en maxheap med följande dataset.
6, 10, 2, 4, 1
Vi kan konstruera ett träd för denna datamängd enligt följande.
I ovanstående trädrepresentation representerar siffrorna inom parentes respektive positioner i matrisen.
För att konstruera en maxhöjd av ovanstående representation måste vi uppfylla heapvillkoret att föräldernoden ska vara större än dess undernoder. Med andra ord måste vi 'heapifiera' trädet för att konvertera det till max-heap.
Efter heapification av ovanstående träd, kommer vi att få max-heap som visas nedan.
Som visas ovan har vi den här maxheapen genererad från en matris.
Därefter presenterar vi en illustration av en högsortering. Efter att ha sett konstruktionen av max-heap hoppar vi över de detaljerade stegen för att konstruera en max-heap och visar direkt maxheapen vid varje steg.
Illustration
Tänk på följande uppsättning element. Vi måste sortera den här matrisen med hjälp av heapsorteringstekniken.
Låt oss konstruera en maxheap som visas nedan för matrisen som ska sorteras.
När högen är konstruerad representerar vi den i en matrisform som visas nedan.
Nu jämför vi 1stnod (root) med den sista noden och byt dem sedan. Således, som visas ovan, byter vi 17 och 3 så att 17 är i den sista positionen och 3 är i den första positionen.
Nu tar vi bort noden 17 från högen och lägger den i den sorterade matrisen som visas i den skuggade delen nedan.
Nu konstruerar vi igen en hög för arrayelementen. Den här gången minskas högstorleken med 1 eftersom vi har tagit bort ett element (17) från högen.
Högen av de återstående elementen visas nedan.
I nästa steg upprepar vi samma steg.
Vi jämför och byter rotelementet och det sista elementet i högen.
Efter byte tar vi bort elementet 12 från högen och flyttar det till den sorterade matrisen.
Återigen konstruerar vi en hög hög för de återstående elementen som visas nedan.
Nu byter vi roten och det sista elementet, dvs 9 och 3. Efter byte raderas element 9 från högen och läggs i en sorterad matris.
Vid den här tiden har vi bara tre element i högen som visas nedan.
Vi byter 6 och 3 och tar bort elementet 6 från högen och lägger till det i den sorterade matrisen.
youtube till mp4-omvandlare online gratis
Nu konstruerar vi en hög med de återstående elementen och byter sedan båda med varandra.
Efter att ha bytt 4 och 3 tar vi bort element 4 från högen och lägger till det i den sorterade matrisen. Nu har vi bara en nod kvar i högen som visas nedan .
Så nu med bara en nod kvar, tar vi bort den från högen och lägger till den i den sorterade matrisen.
Således är ovan visade den sorterade matrisen som vi har erhållit som ett resultat av hop-sorteringen.
I ovanstående illustration har vi sorterat matrisen i stigande ordning. Om vi måste sortera matrisen i fallande ordning måste vi följa samma steg men med min-högen.
Heapsort-algoritmen är identisk med valssortering där vi väljer det minsta elementet och placerar det i en sorterad matris. Heapsortering är dock snabbare än urvalsortering vad gäller prestanda. Vi kan uttrycka det eftersom heapsort är en förbättrad version av sortimentet.
Därefter implementerar vi Heapsort på C ++ och Java-språk.
Den viktigaste funktionen i båda implementeringarna är funktionen ”heapify”. Denna funktion kallas av den huvudsakliga heapsort-rutinen för att ordna om underträdet när en nod raderas eller när max-heap byggs.
När vi har höjt trädet korrekt kommer vi bara att kunna få de rätta elementen i sina rätta positioner och därmed sorteras matrisen korrekt.
bästa spionenheten för mobiltelefoner
C ++ Exempel
Följande är C ++ - koden för heapsort-implementering.
#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 Produktion:
Inmatningsmatris
4 17 3 12 9 6
Sorterad matris
3 4 6 9 12 17
Därefter implementerar vi heapsort på Java-språk
Java-exempel
// 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 Produktion:
Inmatningsmatris:
4 17 3 12 9 6
Sorterad matris:
3 4 6 9 12 17
Slutsats
Heapsort är en jämförelsebaserad sorteringsteknik med binär heap.
Det kan betecknas som en förbättring jämfört med urvalssortering eftersom båda dessa sorteringstekniker fungerar med liknande logik att hitta det största eller minsta elementet i matrisen upprepade gånger och sedan placera det i den sorterade matrisen.
Heap sort använder max-heap eller min-heap för att sortera arrayen. Det första steget i hopsortering är att bygga en min eller max heap från arraydata och sedan radera rotelementet rekursivt och heapify heapen tills det bara finns en nod närvarande i heapen.
Heapsort är en effektiv algoritm och fungerar snabbare än urvalssortering. Den kan användas för att sortera en nästan sorterad matris eller hitta k största eller minsta element i matrisen.
Med detta har vi slutfört vårt ämne om sorteringstekniker i C ++. Från och med nästa handledning börjar vi med datastrukturer en efter en.
=> Leta efter hela C ++ träningsserien här.
Rekommenderad läsning
- MongoDB Sort () -metod med exempel
- Unix Sorteringskommando med syntax, alternativ och exempel
- Slå ihop sortering i C ++ med exempel
- Skalsortering i C ++ med exempel
- Insättningssortering i C ++ med exempel
- Urvalssortering i C ++ med exempel
- Bubblesortering i C ++ med exempel
- Snabbsortering i C ++ med exempel