heap sort c with examples
Een inleiding tot heap-sortering met voorbeelden.
Heapsort is een van de meest efficiënte sorteertechnieken. Deze techniek bouwt een heap op van de opgegeven ongesorteerde array en gebruikt de heap vervolgens opnieuw om de array te sorteren.
Heapsort is een sorteertechniek gebaseerd op vergelijking en maakt gebruik van binaire heap.
Lees de Easy C ++ Training Series door.
impliciet wachten en expliciet wachten in selenium
Wat je leert:
- Wat is een binaire hoop?
- Algemeen algoritme
- Illustratie
- C ++ Voorbeeld
- Java-voorbeeld
- Gevolgtrekking
- Aanbevolen literatuur
Wat is een binaire hoop?
Een binaire heap wordt weergegeven met behulp van een volledige binaire boom. Een complete binaire boom is een binaire boom waarin alle knooppunten op elk niveau volledig zijn gevuld, behalve de bladknooppunten en de knooppunten zijn zover als links.
Een binaire heap of gewoon een heap is een complete binaire boom waarin de items of knooppunten zodanig zijn opgeslagen dat het hoofdknooppunt groter is dan de twee onderliggende knooppunten. Dit wordt ook wel max heap genoemd.
De items in de binaire heap kunnen ook worden opgeslagen als min-heap, waarbij het rootknooppunt kleiner is dan de twee onderliggende knooppunten. We kunnen een hoop voorstellen als een binaire boom of een array.
Terwijl het een heap representeert als een array, ervan uitgaande dat de index begint bij 0, wordt het root-element opgeslagen op 0. In het algemeen, als een bovenliggend knooppunt zich op positie I bevindt, bevindt het linker onderliggende knooppunt zich op de positie (2 * I + 1) en het rechter knooppunt bevindt zich op (2 * I +2).
Algemeen algoritme
Hieronder is het algemene algoritme voor de heap-sorteertechniek weergegeven.
- Bouw een maximale heap op van de gegeven gegevens, zodat de root het hoogste element van de heap is.
- Verwijder de root, d.w.z. het hoogste element van de heap en vervang of verwissel het met het laatste element van de heap.
- Pas vervolgens de max heap aan, om de max heap-eigenschappen niet te schenden (heapify).
- De bovenstaande stap verkleint de heapgrootte met 1.
- Herhaal de bovenstaande drie stappen totdat de heapgrootte is teruggebracht tot 1.
Zoals getoond in het algemene algoritme om de gegeven dataset in oplopende volgorde te sorteren, construeren we eerst een max heap voor de gegeven data.
Laten we een voorbeeld nemen om een max heap samen te stellen met de volgende dataset.
6, 10, 2, 4, 1
We kunnen als volgt een boom voor deze dataset construeren.
In de bovenstaande boomweergave vertegenwoordigen de cijfers tussen haakjes de respectieve posities in de array.
Om een maximale heap van de bovenstaande weergave te construeren, moeten we voldoen aan de heap-voorwaarde dat het bovenliggende knooppunt groter moet zijn dan de onderliggende knooppunten. Met andere woorden, we moeten de boom “heapifyen” om deze naar max-heap te converteren.
Na ophoping van de bovenstaande structuur, krijgen we de max-heap zoals hieronder weergegeven.
Zoals hierboven getoond, hebben we deze max-heap gegenereerd vanuit een array.
Vervolgens presenteren we een illustratie van een hoopsoort. Nadat we de constructie van max-heap hebben gezien, zullen we de gedetailleerde stappen overslaan om een max-heap te construeren en zullen we bij elke stap direct de max heap laten zien.
Illustratie
Beschouw de volgende reeks elementen. We moeten deze array sorteren met behulp van de heap-sorteertechniek.
Laten we een max-heap construeren zoals hieronder weergegeven voor de array die moet worden gesorteerd.
ongedefinieerde referentiefout c ++
Zodra de hoop is opgebouwd, geven we deze weer in een matrixvorm, zoals hieronder weergegeven.
Nu vergelijken we de 1stknooppunt (root) met het laatste knooppunt en wissel ze vervolgens om. Dus, zoals hierboven getoond, wisselen we 17 en 3 zodat 17 zich op de laatste positie bevindt en 3 op de eerste positie.
Nu verwijderen we het knooppunt 17 van de heap en plaatsen het in de gesorteerde array zoals weergegeven in het gearceerde gedeelte hieronder.
Nu construeren we weer een hoop voor de array-elementen. Deze keer wordt de heapgrootte met 1 verkleind omdat we een element (17) uit de heap hebben verwijderd.
De hoop van de overige elementen wordt hieronder weergegeven.
In de volgende stap herhalen we dezelfde stappen.
We vergelijken en wisselen het root-element en het laatste element in de heap uit.
Na het verwisselen verwijderen we het element 12 uit de heap en verplaatsen we het naar de gesorteerde array.
Opnieuw construeren we een max heap voor de overige elementen zoals hieronder getoond.
Nu wisselen we de root en het laatste element, d.w.z. 9 en 3. Na het omwisselen wordt element 9 uit de heap verwijderd en in een gesorteerde array geplaatst.
Op dit moment hebben we slechts drie elementen in de heap, zoals hieronder wordt weergegeven.
We wisselen 6 en 3 om en verwijderen het element 6 van de heap en voegen het toe aan de gesorteerde array.
Nu construeren we een hoop van de resterende elementen en wisselen we beide met elkaar uit.
Nadat we 4 en 3 hebben verwisseld, verwijderen we element 4 van de heap en voegen we het toe aan de gesorteerde array. Nu hebben we nog maar één knooppunt in de heap, zoals hieronder wordt weergegeven
Dus nu met nog maar één knooppunt over, verwijderen we het van de heap en voegen het toe aan de gesorteerde array.
Het bovenstaande is dus de gesorteerde array die we hebben verkregen als resultaat van de heap-sortering.
In de bovenstaande illustratie hebben we de array in oplopende volgorde gesorteerd. Als we de array in aflopende volgorde moeten sorteren, moeten we dezelfde stappen volgen, maar met de min-heap.
Heapsort-algoritme is identiek aan selectiesortering, waarbij we het kleinste element selecteren en in een gesorteerde array plaatsen. Heap-sortering is echter sneller dan selectiesortering voor zover het de prestaties betreft. We kunnen het zeggen zoals Heapsort een verbeterde versie is van de selectiesortering.
Vervolgens zullen we Heapsort implementeren in C ++ en Java-taal.
De belangrijkste functie in beide implementaties is de functie “heapify”. Deze functie wordt aangeroepen door de hoofdheapsort-routine om de substructuur te herschikken zodra een knooppunt is verwijderd of wanneer max-heap is gebouwd.
Als we de boom correct hebben opgehoopt, kunnen we alleen de juiste elementen op hun juiste posities krijgen en zal de array dus correct worden gesorteerd.
C ++ Voorbeeld
Hieronder volgt de C ++ -code voor de implementatie van Heapsort.
Uitgang:
Invoerarray
4 17 3 12 9 6
Gesorteerde array
3 4 6 9 12 17
Vervolgens zullen we de Heapsort in Java-taal implementeren
Java-voorbeeld
Uitgang:
Invoerarray:
4 17 3 12 9 6
shell scripting interviewvragen en antwoorden
Gesorteerde array:
3 4 6 9 12 17
Gevolgtrekking
Heapsort is een op vergelijking gebaseerde sorteertechniek met behulp van binaire heap.
Het kan worden genoemd als een verbetering ten opzichte van selectiesortering, aangezien beide sorteertechnieken werken met dezelfde logica om het grootste of kleinste element in de array herhaaldelijk te vinden en het vervolgens in de gesorteerde array te plaatsen.
Heap-sortering maakt gebruik van max-heap of min-heap om de array te sorteren. De eerste stap bij het sorteren van de heap is om een min of max heap op te bouwen uit de array-gegevens en vervolgens het root-element recursief te verwijderen en de heap te heapificeren totdat er slechts één knooppunt in de heap aanwezig is.
Heapsort is een efficiënt algoritme en werkt sneller dan het sorteren van selecties. Het kan worden gebruikt om een bijna gesorteerde array te sorteren of om k grootste of kleinste elementen in de array te vinden.
Hiermee hebben we ons onderwerp over sorteertechnieken in C ++ afgerond. Vanaf onze volgende tutorial beginnen we één voor één met datastructuren.
Zoek hier de volledige C ++-trainingsserie.
Aanbevolen literatuur
- MongoDB Sort () -methode met voorbeelden
- Unix-sorteeropdracht met syntaxis, opties en voorbeelden
- Sorteer samenvoegen in C ++ met voorbeelden
- Shell-sortering in C ++ met voorbeelden
- Invoegsortering in C ++ met voorbeelden
- Selectie sorteren in C ++ met voorbeelden
- Bubbelsortering in C ++ met voorbeelden
- Snel sorteren in C ++ met voorbeelden