Uvod v razvrščanje gomile v C ++
Heapsort je ena od primerjalnih tehnik sortiranja in je del selekcijske sorte. Kjer je razvrščanje opredeljeno kot urejanje nizov podatkov v določenem zaporedju z uporabo edinstvene vrednosti, ki je znana kot ključni element na danem seznamu. Izraz razvrščanje je bil uveden, ko so ljudje spoznali pomen iskanja katerega koli elementa v katerem koli naboru informacij, sicer bi bilo zelo težko iskati po katerem koli zapisu, če bi bil neurejen in odkrit.
Pri razvrščanju je veliko različnih tehnik, ki imajo svojo učinkovitost v času, potrebnem za razvrščanje danih podatkov in potrebe po prostoru v pomnilniku. So razvrščanje mehurčkov, sortiranje vstavitve, izbira sorte, hitro sortiranje, združevanje in razvrščanje po vrsti.
Kaj je sorta grozdja?
Heapsort je način razvrščanja, ki temelji na strukturi podatkov binarne kopice, podobno izbiri sortiranja, kjer najprej pridobimo največji del podatkovnega niza in ga postavimo na konec ter nadaljujemo z ostalimi elementi.
Heapsort kot že samo ime pove. Najprej sestavi kopica podatkovnih elementov iz danega nesortiranega niza, nato pa preveri, ali je največji element postavljen na konec delno razvrščenega niza. Ponovno obnovi kopico, poišče naslednji največji zapis in ga položi v naslednji prazen utor s konca na pol razvrščene plošče. Ta postopek se ponovi, dokler v kopici ne ostane nobenih predmetov. Ta tehnika zahteva dva niza, enega za shranjevanje kopice, drugega pa za razvrščen niz.
Algoritam heap Razvrsti v C ++
- Najprej izberite koren kot povišen element iz danega nabora informacij, da ustvarite največjo množico.
- Rekonstruirajte kopico tako, da postavite ali zamenjate koren z zadnjim elementom.
- Velikost kopice se bo zdaj zmanjšala za 1.
- Nato spet naredimo kopico s preostalimi elementi in nadaljujemo, dokler se velikost kopice ne zmanjša na 1.
Primer razvrščanja gomile v C ++
Ta tehnika uporablja binarno kopico, ki je izdelana z uporabo celotnega binarnega drevesa, kjer je koreninsko vozlišče večje od njegovih dveh otroških vozlišč.
Razmislite o podanem nizu podatkovnih nizov.
Pojdimo po algoritmu. Pravi, da kot koren izberemo najvišji element in zgradimo največjo kopico.
1. Prva ponovitev
Zdaj bo matrika oblika:
Zdaj bo razvrščeni niz v obliki:
Velikost kopice se bo zmanjšala za 1, zdaj je 6-1 = 5.
2. Druga ponovitev
Torej zdaj kup izgleda:
Niz je v obliki:
Razvrščeni niz bo:
Velikost kopice se bo zmanjšala za 1, zdaj je 5-1 = 4.
3. Tretja Iteracija
Nova kopica izgleda kot:
Niz je v obliki:
Razvrščeni niz bo:
Velikost kopice se bo zmanjšala za 1, zdaj 4-1 = 3.
4. Četrta Iteracija
Nova kopica izgleda kot:
Niz je v obliki:
Razvrščeni niz bo:
Velikost kopice se bo zmanjšala za 1, zdaj je 3-1 = 2.
5. Peta Iteracija
Nova kopica izgleda kot:
Niz je v obliki:
Razvrščeni niz bo:
Velikost kopice se bo zmanjšala za 1, zdaj je 2-1 = 1.
6. Zadnja ponovitev
Nova kopica izgleda tako:
Niz ima:
4
Iz algoritma smo izvedli vse korake, dokler velikost kopice ni 1. Torej imamo zdaj razvrščeno matriko:
Zato je razvrščeni niz največje kopice v naraščajočem vrstnem redu. Če potrebujemo matriko razvrščeno po padajočem vrstnem redu, sledimo zgornjim korakom z minimalno množico.
Program C ++ za razvrščanje kopice je naveden spodaj:
#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);
)
Izhod:
Zaključek
Heapsort je tehnika, ki temelji na primerjavi, ki izboljšuje selekcijsko razvrščanje. Razvrstitev v heap uporabi izbiro najvišjega ali najnižjega elementa v dani matriki, da se razvrsti po naraščajočem ali padajočem vrstnem redu z največjo ali najmanjšo kopico. Izvedite ta postopek, dokler ne dobimo enega v velikosti kopice. Ta tehnika razvrščanja se uporablja tudi za iskanje največjega in najnižjega elementa v matriki. Tehnika razvrščanja v kopici je učinkovitejša in hitrejša od tehnike izbire.
Priporočeni članki
To je vodnik za razvrščanje gomile v C ++. Tu razpravljamo o tem, kaj je vrsta heap v c ++, ki deluje z njegovim algoritmom in Example. Če želite izvedeti več, si oglejte tudi naslednje članke -
- Razvrstite v C
- Razvrsti po Javi
- Preobremenitev v C ++
- Kazalniki v C ++
- Preobremenitev na Javi