Triedenie výberom

Heap Sort je triediaci algoritmus, ktorý na triedenie využíva dátovú štruktúru binárna hromada. Celé triedenie spočíva v tom, že si algoritmus najskôr zo vstupného poľa vytvorí binárnu hromadu a následne postupným mazaním všetkých jej prvkov toto pole utriedi.

Hromada, ktorú využívame pri Heap Sorte musí spĺňať nasledovné podmienky:

1. Vrchol hromady (root) je vždy prvý prvok v poli (v našom prípade prvok na 0-tej pozícii).

2. Pre ľubovoľný prvok uložený na indexe [math]i[/math] z intervalu [math] \langle 0 \ ; \ \text{dĺžka} - 1 \rangle [/math] platia nasledovné rovnice:

[math] \begin{align} \text{ľavý potomok} &= 2i + 1 && (1) \\ \text{pravý potomok} &= 2i + 2 && (2) \\ \text{rodič} &= \left \lfloor \frac{i - 1}{2} \right \rfloor \quad (\text {okrem} \ i = 0) && (3) \end{align} [/math]

3. Každý prvok (uzol) v hromade musí mať väčšiu, alebo rovnakú hodnotu ako jeho potomkovia (MAX HEAP - ak triedime pole vzostupne, v opačnom prípade by sme použili MIN HEAP).

Algoritmus Heapify

vizualizácia

Heapify je kľúčovým podprogramom triediaceho algoritmu Heap Sort, vďaka ktorému vieme efektíve zabezpečiť vytvorenie a zmazanie hromady.

Ak máme i-ty prvok v poli (v kompletnom binárnom strome), ktorého potomkovia tvoria dve samostatné podhromady, potom funkcia Heapify zlúči tieto dve podhromady do jednej hromady, pričom i-ty prvok bude jej vrcholom.

Vlastnosti algoritmu

dátová štruktúra: hromada (reprezentovaná ako: pole, strom)
časová zložitosť: lineárna [math]O(n)[/math]
priestorová zložitosť: konštantná [math]O(1)[/math] pri iteračnej verzii, [math]O(log(N))[/math] pri rekurzívnej verzii

Základné časti algoritmu

Určenie potomka s maximálnou hodnotou i-teho prvku.
Porovnanie maximálneho potomka s rodičom (i-tym prvkom).
Ak je potomok väčší ako rodič, tak výmena potomka a rodiča.
Ak nastala výmena, skontrolovanie ovplyvneného potomka (podstromu).

Slovný opis algoritmu

Dostaneme na vstupe pole a index i, v ktorom chceme vytvoriť hromadu. Najskôr skontrolujeme, či prvok na indexe i má nejakých potomkov (využijeme rovnice (1) a (2)). Ak nemá žiadnych potomkov, funkcia skončí, pretože i predstavuje jednoprvkovú hromadu. Ak má práve jedného potomka, tento potomok je zároveň maximálnym potomkom. Ak má práve dvoch potomkov, tak z nich vyberieme maximálneho potomka. Následne Skontrolujeme veľkosť maximálneho potomka a jeho rodiča (prvok na indexe i). Ak je rodič väčší, funkcia skončí, pretože prvok i predstavuje vrchol hromady. Ak nie, vymeníme rodiča a maximálneho potomka. Ak nastala výmena, musíme skontrolovať ovplyvnenú podhromadu, tj. zopakovať tento sled krokov pre podhromadu, ktorej vrchol bude v maximálnom potomkovi i-teho prvku.

Z hľadiska implementácie môžeme vytvoriť iteračnú aj rekurzívnu verziu.

Pseudokód

Iteračná verziaRekurzívna verzia

Nech funkcia Heapify má nasledovný prototyp Heapify(pole[], dlzka, i)

1. Je 2 * i + 1 < dlzka ? Ak áno, pokračuj krokom 1.1., inak skonči.

1.1. Nech: lavy = 2 * i + 1

1.2. Nech: pravy = 2 * i + 2

1.3. Je pravy < dlzka a zároveň pole[pravy] > pole[lavy] ?

Ak áno:

1.3.1. Nech: max = pravy

Ak nie:

1.3.1. Nech: max = lavy

1.4. Je pole[max] > pole[i] ?

Ak áno:

1.4.1. Vymeň: pole[max] a pole[i]

1.4.2. i = max

Ak nie:

1.4.1 Skonči.

2. Skoč na krok 1.

Nech funkcia Heapify má nasledovný prototyp Heapify(pole[], dlzka, i)

1. Je pole[2 * i + 1] >= pole[2 * i + 2] ?

Ak áno:

1.1. Nech: max = pole[2 * i + 1]

Ak nie:

1.1. Nech: max = pole[2 * i + 2]

2. Je pole[max] > pole[i] ?

Ak áno:

2.1. Vymeň: pole[i] a pole[max]

2.2. Rekurzívne zavolaj: Heapify(pole[], dlzka, max)

Ak nie:

2.1. Skonči volanie.

Algoritmus Heap Sort

Heapsort pri triedení vykonáva dve základné úlohy: Vytvorenie maximálnej binárnej hromady zo vstupného poľa a mazanie jednotlivých prvkov z hromady. Pri oboch procedúrach využíva algoritmus Heapify

Vlastnosti algoritmu

vhodný pre dátové štruktúry: pole
časová náročnosť: vždy linearitmická [math] O(n\log(n)) [/math], vďaka ktorej dokáže efektívne triediť veľmi veľké polia
priestorová náročnosť: konštantná [math]O(1)[/math] pri iteračnej verzii, logaritmická [math]O(\log(n))[/math] pri rekurzívnej verzii.
druh triedenia: triedenie výberom (komparačný algoritmus)
stabilita triedenia: nestabilný
miesto triedenia: vnútorné triedenie

Implementácia algoritmov Heapify a HeapSort v rôznych programovacích jazykoch

Iteračná CRekurzívna C

#include <stdio.h>

void Vymen(int *a, int *b);
void Heapify(int pole[], int dlzka, int index);
void HeapSort(int pole[], int dlzka);

int main()
{
    int pole[]= {10, 5, 2, 9, 8, 7, 1, 3, 4, 0, -1};
    int dlzka = sizeof(pole) / sizeof(pole[0]);

    HeapSort(pole, dlzka);

    for (int i = 0; i < dlzka; ++i)
    {
        printf("%d ", pole[i]);
    }
}


void Vymen(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void Heapify(int pole[], int dlzka, int index)
{
    int pravy, lavy, max;

    while(2 * index + 1 < dlzka)
    {
        lavy = 2 * index + 1;
        pravy = 2 * index + 2;

        // určenie potomka s maximálnou hodnotou
        if(pravy < dlzka && pole[pravy] > pole[lavy])
        {
            max = pravy;
        }
        else
        {
            max = lavy;
        }

        // porovnanie maximálneho potomka s rodičom
        if(pole[max] > pole[index])
        {

            Vymen(&pole[max], &pole[index]);
            index = max;
        }
        else
        {
            return;
        }
    }
}

void HeapSort(int pole[], int dlzka)
{
    // vytvor  maximálnu hromadu (procedúra BuildMaxHeap)
    for (int i = dlzka / 2 - 1 ; i >= 0; --i)
    {
        Heapify(pole, dlzka, i);
    }

    // zmaž všetky prvky z hromady
    for (int j = dlzka - 1; j > 0; --j)
    {
        Vymen(&pole[0], &pole[j]);
        Heapify(pole, j, 0);
    }
}

#include <stdio.h>

void Vymen(int *a, int *b);
void Heapify(int pole[], int dlzka, int index);
void HeapSort(int pole[], int dlzka);

int main()
{
    int pole[]= {10, 5, 2, 9, 8, 7, 1, 3, 4, 0, -1, -1};
    int dlzka = sizeof(pole) / sizeof(pole[0]);

    HeapSort(pole, dlzka);

    for (int i = 0; i < dlzka; ++i)
    {
        printf("%d ", pole[i]);
    }
}


void Vymen(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void Heapify(int pole[], int dlzka, int index)
{

        int lavy = 2 * index + 1;
        int pravy = 2 * index + 2;
        int max = index;

        // určenie potomka s maximálnou hodnotou
        if(lavy < dlzka && pole[lavy] >= pole[pravy])
        {
            max = lavy;
        }

        if(pravy < dlzka && pole[pravy] > pole[lavy])
        {
            max = pravy;
        }

        // porovnanie maximálneho potomka s rodičom
        if(pole[max] > pole[index])
        {
            Vymen(&pole[max], &pole[index]);
            Heapify(pole, dlzka, max);
        }
}

void HeapSort(int pole[], int dlzka)
{
    // vytvor  maximálnu hromadu (procedúra BuildMaxHeap)
    for (int i = dlzka / 2 - 1 ; i >= 0; --i)
    {
        Heapify(pole, dlzka, i);
    }

    // zmaž všetky prvky z hromady
    for (int j = dlzka - 1; j > 0; --j)
    {
        Vymen(&pole[0], &pole[j]);
        Heapify(pole, j, 0);
    }
}

Selection Sort

Odkazy

https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_heapify_method.htm

Triedenie výberom

Obsah

Tento článok je v prvotnom štádiu konštrukcie, zatiaľ je to len hromada myšlienok :)

Heap Sort

Prehľad

Algoritmus Heapify

Vlastnosti algoritmu

Základné časti algoritmu

Slovný opis algoritmu

Pseudokód

Algoritmus Heap Sort

Vlastnosti algoritmu

Implementácia algoritmov Heapify a HeapSort v rôznych programovacích jazykoch

Selection Sort

Odkazy

Navigačné menu

Osobné nástroje

Menné priestory

Varianty

Zobrazenia

Viac

Hľadať

Navigácia

Rýchle linky

Nástroje