Úvod do triedenia haldy v C ++

Heapsort je jednou z triediacich techník založených na porovnaní a je súčasťou triedenia výberu. Ak je triedenie definované ako usporiadanie súborov údajov v určitom špecifickom poradí pomocou jedinečnej hodnoty známej ako kľúčový prvok v danom zozname. Pojem triedenie bol zavedený, keď ľudia spoznali dôležitosť prehľadávania akéhokoľvek prvku v ktorejkoľvek danej skupine informácií, inak by bolo veľmi ťažké vyhľadať akýkoľvek záznam, ak by bol neusporiadaný a netriedený.

Pri triedení existuje veľa rôznych techník, z ktorých každá má svoju príslušnú účinnosť v čase potrebnom na triedenie daných údajov a požiadavky na miesto v pamäti. Sú to bublinové, vkladacie, výberové, rýchle, zlúčené a haldy.

Čo je triedenie haldy?

Heapsort je prístup triedenia založený na dátovej štruktúre binárnych haldy, podobný výberu triedenia, kde najprv získame maximálny kus dátovej sady a umiestnime ju na koniec a pokračujeme po zvyšok prvkov.

Heapsort, ako už názov napovedá. Najprv vytvorí hromadu dátových prvkov z daného netriedeného poľa a potom skontroluje najväčšiu položku a umiestni ju na koniec čiastočne zoradeného poľa. Opäť prestaví haldu, vyhľadá ďalšiu najväčšiu časť záznamu a umiestni ju do ďalšieho prázdneho slotu od konca polotriedeného usporiadania záznamov. Tento proces sa opakuje dovtedy, kým v halde nezostanú žiadne položky. Táto technika vyžaduje dve polia pre uloženie haldy a pre triedené pole.

Algoritmus haldy Zoradiť v C ++

  • Najskôr vyberte root ako vyvýšený prvok z danej množiny informácií, aby ste vytvorili maximálnu hromadu.
  • Zrekonštruujte haldu umiestnením alebo výmenou koreňa s posledným prvkom.
  • Veľkosť haldy sa teraz zmenší o 1.
  • Potom znova vytvoríme haldu so zostávajúcimi prvkami a pokračujeme, kým sa veľkosť haldy nezníži na 1.

Príklad usporiadania haldy v C ++

Táto technika používa binárnu haldu, ktorá je vytvorená pomocou úplného binárneho stromu, kde je koreňový uzol väčší ako jeho dva podriadené uzly.

Zvážte danú škálu súborov údajov.

Poďme podľa algoritmu. Hovorí sa, že vyberie najvyšší prvok ako root a zostaví maximálnu haldu.

1. Prvá iterácia

Teraz bude mať pole podobu:

Teraz bude mať zoradené pole podobu:

Veľkosť haldy sa zníži o 1, teraz 6-1 = 5.

2. Druhá iterácia

Hromada teraz vyzerá takto:

Pole má podobu:

Zoradené pole bude:

Veľkosť haldy sa zníži o 1, teraz 5-1 = 4.

3. Tretia iterácia

Nová hromada vyzerá takto:

Pole má podobu:

Zoradené pole bude:

Veľkosť haldy sa zníži o 1, teraz 4-1 = 3.

4. Štvrtá itrácia

Nová hromada vyzerá takto:

Pole má podobu:

Zoradené pole bude:


Veľkosť haldy sa zníži o 1, teraz 3-1 = 2.

5. Piata itrácia

Nová hromada vyzerá takto:

Pole má podobu:

Zoradené pole bude:

Veľkosť haldy sa zníži o 1, teraz 2-1 = 1.

6. Posledná iterácia

Nová hromada vyzerá takto:

Pole má:

4

Z algoritmu sme vykonali všetky kroky, kým veľkosť haldy nebude 1. Takže teraz máme zoradené pole:


Zoradené pole maximálnej haldy je preto vzostupne. Ak potrebujeme, aby bolo pole zoradené zostupne, potom postupujte podľa vyššie uvedených krokov s minimálnym haldy.

Program C ++ pre triedenie haldy je uvedený nižšie:

#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);
)

Výkon:

záver

Heapsort je technika založená na porovnávaní, ktorá je vylepšením triedenia výberu. Usporiadanie haldy využíva výber najvyššieho alebo najnižšieho prvku v danom poli na zoradenie vzostupne alebo zostupne podľa maximálneho alebo minimálneho haldy. Vykonajte tento proces, až kým ho nezískame ako veľkosť haldy. Táto technika triedenia sa používa aj na nájdenie najväčšieho a najnižšieho prvku v poli. Technika triedenia haldy je efektívnejšia a rýchlejšia ako technika triedenia výberu.

Odporúčané články

Toto je sprievodca triedením haldy v jazyku C ++. Tu diskutujeme o tom, čo je halda triediť v c ++, pracovať s jeho algoritmom a príkladom. Viac informácií nájdete aj v nasledujúcich článkoch

  1. Halda Zoradiť podľa C.
  2. Usporiadanie haldy v Jave
  3. Preťaženie v C ++
  4. Ukazovatele v jazyku C ++
  5. Preťaženie v Jave

Kategórie:

Vývoj softvéru