Bevezetés a halomfajtához a C ++ kategóriában

A Heapsort az összehasonlításon alapuló válogatás egyik technikája, és része a szelekciónak. Ahol a válogatást úgy definiálják, mint az adatkészletek bizonyos sorrendben történő rendezése az adott listában kulcsfontosságú elemként ismert egyedi érték felhasználásával. A válogatás kifejezést azért vezették be, amikor az emberek megismerték az információhalmaz bármely elemére való keresés fontosságát, különben nagyon nehéz lenne bármelyik rekordból keresni, ha rendezetlen és válogatás nélküli.

Számos különféle módszer létezik a válogatásban, amelyek mindegyikének megvan a maga hatékonysága az adott adatok és a memória tárolására vonatkozó adatok rendezéséhez szükséges időben. Ezek buborékrendezés, beillesztési rendezés, válogatási rendezés, gyors rendezés, egyesítés és halom rendezés.

Mi a Heap Sort?

A Heapsort egy olyan válogatási megközelítés, amely a bináris halom adatstruktúrán alapul, mint a szelekciós rendezés, ahol először megkapjuk a maximális adatkészletet, és a végére helyezzük, és a többi elemhez folytatjuk.

Heapsort, ahogy a neve maga is sugallja. Először felépíti az adatelemek halomát az adott válogatott tömbből, majd ellenőrzi a legnagyobb elemet és elhelyezi a részben rendezett tömb végére. Ismét újjáépíti a halomot, keresi a következő legnagyobb darab darabot, és a lemezek félig rendezett elrendezésének végétől a következő üres nyílásba helyezi. Ezt a folyamatot addig ismételjük, amíg egyetlen elem sem marad a halomban. Ehhez a technikához két tömb szükséges, az egyik a halom tárolására, a másik egy válogatott tömb számára.

Halom algoritmusa Rendezés C ++-ban

  • Először válassza ki a gyökér emelt elemként elemet az adott információelemekből, hogy maximális halom legyen.
  • Helyezze újra a halomot úgy, hogy a gyököt az utolsó elemre helyezi vagy felcserélte.
  • A kupac mérete most 1-rel csökken.
  • Ezután ismét megteremtjük a kupacot a megmaradt elemekkel és folytatjuk, amíg a kupac mérete 1-re csökken.

Példa a halom rendezésére C ++-ban

Ez a technika bináris halomot használ, amelyet egy teljes bináris fa felhasználásával állítanak elő, ahol a gyökér csomópont nagyobb, mint a két gyermek csomópontja.

Vegye figyelembe az adatkészletek adott tömbjét.

Menjünk az algoritmus szerint. Azt mondja, hogy válassza ki a legmagasabb elemet gyökérként, és állítsa össze a maximális halom értéket.

1. Első iteráció

A tömb mostantól a következőképp lesz:

Most a rendezett tömb a következő formában lesz:

A kupac méretét 1-rel, most 6-1 = 5-rel csökkentik.

2. Második ismétlés

Tehát most a halom néz ki:

A tömb formája:

A rendezett tömb a következő lesz:

A kupac méretét 1-rel, most 5-1 = 4-rel csökkentik.

3. Harmadik ismétlés

Az új halom így néz ki:

A tömb formája:

A rendezett tömb a következő lesz:

A kupac méretét 1-rel csökkentik, most 4-1 = 3-ra.

4. Negyedik ismétlés

Az új halom így néz ki:

A tömb formája:

A rendezett tömb a következő lesz:


A kupac méretét 1-rel, most 3-1 = 2-rel csökkentik.

5. Ötödik megismételés

Az új halom így néz ki:

A tömb formája:

A rendezett tömb a következő lesz:

A kupac méretét 1-rel, most 2-1 = 1-rel csökkentik.

6. Utolsó megismételés

Az új halom így néz ki:

A tömbnek van:

4

Az algoritmus alapján minden lépést elvégeztünk, amíg a halom mérete 1-nek nem áll. Tehát most van a rendezett tömb:


Ezért a maximális halom rendezett tömbje növekvő sorrendben van. Ha csökkenő sorrendben van szükségünk a tömbre, akkor kövesse a fenti lépéseket minimális halommennyiséggel.

C ++ program a halomfajták rendezéséhez az alábbiak szerint:

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

Kimenet:

Következtetés

A Heapsort az összehasonlításon alapuló technika, amely javítja a szelekciós rendezést. A halomrendezés az adott tömb legmagasabb vagy legalacsonyabb elemét választja ki, hogy növekvő vagy csökkenő sorrendben rendezzen, a maximális vagy a minimális halom alapján. Végezzük ezt a folyamatot mindaddig, amíg halom méretű lesz. Ezt a válogatási technikát a tömb legnagyobb és legalacsonyabb elemének megtalálására is használják. A halom rendezési technika hatékonyabb és gyorsabb, mint a szelekciós rendezési technika.

Ajánlott cikkek

Ez egy útmutató a Heap Sort C ++ alkalmazásban. Itt tárgyaljuk, mi a c ++ halomfajta, az algoritmussal és a példával együtt. A következő cikkeket is megnézheti további információkért -

  1. Halom C sorrendben
  2. Heap Sort in Java
  3. Túlterhelés a C ++ kategóriában
  4. C ++ mutatók
  5. Túlterhelés a Java-ban

Kategória:

Szoftverfejlesztés