Inleiding tot Heap Sort in C ++
Heapsort is een van de op vergelijking gebaseerde sorteertechnieken en maakt deel uit van de selectiesortering. Waar sorteren wordt gedefinieerd als het ordenen van gegevenssets in een bepaalde volgorde met behulp van een unieke waarde die bekend staat als een sleutelelement in de gegeven lijst. De term sortering werd geïntroduceerd toen mensen het belang van het zoeken naar elk element in een gegeven set van informatie leerden kennen, het zou heel moeilijk zijn om in elk record te zoeken als het ongeordend en ongesorteerd was.
Er zijn veel verschillende technieken betrokken bij het sorteren, die elk hun respectieve efficiëntie hebben in de tijd die nodig is om de gegeven gegevens en de vereiste ruimte in het geheugen te sorteren. Ze zijn bubbelsortering, invoegsortering, selectiesortering, snel sorteren, samenvoegen sorteren en heap sorteren.
Wat is Heap Sort?
Heapsort is een sorteerbenadering op basis van de binaire heap-gegevensstructuur vergelijkbaar met selectiesortering, waarbij we eerst de maximale gegevensset verkrijgen en deze aan het einde plaatsen en doorgaan voor de rest van de elementen.
Heapsort zoals de naam zelf al doet vermoeden. Het bouwt eerst de heap van data-elementen uit de gegeven ongesorteerde array en controleert vervolgens op het grootste item en plaatst het aan het einde van de gedeeltelijk gesorteerde array. Het bouwt de heap opnieuw op, zoekt naar het volgende grootste stuk records en plaatst het in de volgende lege sleuf vanaf het einde van de half gesorteerde rangschikking van records. Dit proces wordt herhaald totdat er geen items meer in de heap zijn. Deze techniek vereist twee arrays, één voor het opslaan van de heap en de andere voor een gesorteerde array.
Algoritme van Heap Sort in C ++
- Kies eerst root als een verhoogd element uit de gegeven informatieset van elementen om een maximale heap te creëren.
- Reconstrueer de heap door de wortel te plaatsen of uit te wisselen met het laatste element.
- De heapgrootte krimpt nu met 1.
- Vervolgens maken we de heap opnieuw met de resterende elementen en gaan we door totdat de heapgrootte is verkleind tot 1.
Voorbeeld van heap-sortering in C ++
Deze techniek maakt gebruik van binaire heap die is geconstrueerd met behulp van een complete binaire boom waarvan de wortelknoop groter is dan zijn twee kinderknopen.
Overweeg de gegeven reeks gegevenssets.
Laten we gaan volgens het algoritme. Het zegt om het hoogste element als de wortel te selecteren en de maximale heap te construeren.
1. Eerste herhaling
De array heeft nu de vorm:
Nu zal de gesorteerde array de volgende vorm hebben:
De heapgrootte wordt met 1 verkleind, nu 6-1 = 5.
2. Tweede herhaling
Dus nu ziet de hoop eruit als:
De array heeft de vorm:
De gesorteerde array is:
De heapgrootte wordt met 1 verkleind, nu 5-1 = 4.
3. Derde herhaling
De nieuwe hoop ziet eruit als:
De array heeft de vorm:
De gesorteerde array is:
De heapgrootte wordt met 1 verkleind, nu 4-1 = 3.
4. Vierde herhaling
De nieuwe hoop ziet eruit als:
De array heeft de vorm:
De gesorteerde array is:
De heapgrootte wordt met 1 verkleind, nu 3-1 = 2.
5. Vijfde herhaling
De nieuwe hoop ziet eruit als:
De array heeft de vorm:
De gesorteerde array is:
De heapgrootte wordt met 1 verkleind, nu 2-1 = 1.
6. Laatste herhaling
De nieuwe hoop ziet eruit als:
De array heeft:
4
Vanuit het algoritme hebben we alle stappen uitgevoerd tot de heapgrootte 1 is. We hebben nu de gesorteerde array:
Daarom is de gesorteerde array van de maximale heap in oplopende volgorde. Als we de array in aflopende volgorde moeten sorteren, volg dan de bovenstaande stappen met een minimale heap.
C ++ programma voor heap sort is zoals hieronder gegeven:
#include
using namespace std;
void heapify(int arr(), int n, int i)
(
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l arr(largest))
largest = l;
if (r arr(largest))
largest = r;
if (largest != i) (
swap(arr(i), arr(largest));
heapify(arr, n, largest);
)
)
void heapSort(int arr(), int n)
(
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--)
(
swap(arr(0), arr(i));
heapify(arr, i, 0);
)
)
void printArray(int arr(), int n)
(
for (int i = 0; i < n; ++i)
cout << arr(i) << " ";
cout << "\n";
)
int main()
(
int arr() = ( 5, 18, 4, 13, 10, 7);
int n = sizeof(arr) / sizeof(arr(0));
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
)
Output:
Conclusie
Heapsort is de op vergelijking gebaseerde techniek die de verbetering van selectiesortering is. Heap-sortering maakt gebruik van het selecteren van het hoogste of laagste element in de gegeven array om te sorteren in oplopende of aflopende volgorde, respectievelijk met de maximale of minimale heap. Voer dit proces uit totdat we er één als heapgrootte krijgen. Deze sorteertechniek wordt ook gebruikt om het grootste en laagste element in de reeks te vinden. De heap-sorteertechniek is efficiënter en sneller dan de selectie-sorteertechniek.
Aanbevolen artikelen
Dit is een gids voor Heap Sort in C ++. Hier bespreken we wat heap sort is in c ++, waarbij we werken met zijn algoritme en Voorbeeld. U kunt ook de volgende artikelen bekijken voor meer informatie-
- Heap Sorteer in C
- Heap Sort In Java
- Overbelasting in C ++
- Aanwijzers in C ++
- Overbelasting in Java