Introduktion till Heap Sort in C ++
Heapsort är en av de jämförelsebaserade sorteringsteknikerna och är en del av urvalsorten. Där sortering definieras som att ordna datauppsättningar i någon specifik ordning med unikt värde känt som ett nyckelelement i den givna listan. Termen sortering infördes när människor fick veta vikten av att söka efter något element i en viss uppsättning information annars, det skulle vara mycket svårt att söka i någon post om den var oordnad och osorterad.
Det finns många olika tekniker involverade i sortering av var och en med sin respektive effektivitet under den tid det tar för att sortera den givna informationen och kravet på utrymme i minnet. De är bubbelsortering, insättningssortering, urvalssortering, snabbsortering, sammanslagningssortering och högsortering.
Vad är Heap Sort?
Heapsort är en sorteringsmetod baserad på den binära heapdatastrukturen som liknar valssortering där vi först får den maximala datamängden och placerar den i slutet och fortsätter för resten av elementen.
Heapsort som namnet självt antyder. Den bygger först högen av dataelement från den givna osorterade matrisen och kontrollerar sedan efter den största artikeln och placerar den i slutet av den delvis sorterade matrisen. Det bygger igen högen, söker efter nästa största skiva och placerar den i nästa tomma kortplats från slutet av det halvsorterade arrangemanget av poster. Denna process upprepas tills det inte finns några poster kvar i högen. Denna teknik kräver två matriser en för lagring av högen och den andra för en sorterad matris.
Algoritm of Heap Sortera i C ++
- Välj först rot som ett upphöjd element från den givna informationsuppsättningen av element för att skapa en maximal hög.
- Rekonstruera högen genom att placera eller byta ut roten med det sista elementet.
- Heapstorleken krymper nu med 1.
- Sedan gör vi igen högen med återstående element och fortsätter tills högstorleken minskas till 1.
Exempel på Heap Sort i C ++
Denna teknik använder binär hög som är konstruerad med hjälp av ett komplett binärt träd där rotnoden är större än dess två barnnoder.
Tänk på det givna utbudet av datamängder.
Låt oss gå enligt algoritmen. Det står att välja det högsta elementet som roten och konstruera den maximala högen.
1. Första Iteration
Nu kommer matrisen att ha formen:
Nu kommer den sorterade matrisen att ha formen:
Heapstorleken reduceras med 1, nu 6-1 = 5.
2. Andra Iteration
Så nu ser högen ut:
Matrisen är av formen:
Den sorterade matrisen är:
Heapstorleken kommer att reduceras med 1, nu 5-1 = 4.
3. Tredje Iteration
Den nya högen ser ut:
Matrisen är av formen:
Den sorterade matrisen är:
Heapstorleken kommer att reduceras med 1, nu 4-1 = 3.
4. Fjärde Iteration
Den nya högen ser ut:
Matrisen är av formen:
Den sorterade matrisen är:
Heapstorleken kommer att reduceras med 1, nu 3-1 = 2.
5. Femte Iteration
Den nya högen ser ut:
Matrisen är av formen:
Den sorterade matrisen är:
Heapstorleken kommer att reduceras med 1, nu 2-1 = 1.
6. Sista Iteration
Den nya högen ser ut:
Arrayen har:
4
Från algoritmen har vi genomfört alla stegen tills högstorleken är 1. Så nu har vi den sorterade matrisen:
Därför är den sorterade matrisen för den maximala högen i stigande ordning. Om vi behöver matrisen sorterad i fallande ordning, följ sedan ovanstående steg med en minimal hög.
C ++ -program för heap sort är som anges nedan:
#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);
)
Produktion:
Slutsats
Heapsort är den jämförelsebaserade tekniken som är förbättringen av urvalssortering. Heap sortering använder sig av att välja det högsta eller lägsta elementet i den givna arrayen för att sortera i stigande respektive fallande ordning med den maximala eller minimala högen. Utför denna process tills vi får en som högstorlek. Denna sorteringsteknik används också för att hitta det största och lägsta elementet i matrisen. Heapsorteringstekniken är effektivare och snabbare än urvalsorteringstekniken.
Rekommenderade artiklar
Detta är en guide till Heap Sort in C ++. Här diskuterar vi vad som är heap sort i c ++ och arbetar med dess algoritm och exempel. Du kan också titta på följande artiklar för att lära dig mer-
- Heap Sort in C
- Heap Sort In Java
- Överbelastning i C ++
- Pekare i C ++
- Överbelastning i Java