Triedenie výberom: Rozdiel medzi revíziami

Heap Sort je triediaci algoritmus, ktorý podobne ako Selection sort rozeľuje pole na zotriedenú a nezotriedenú časť, pričom nezotriedená časť predstavuje dátovú štruktúru binárna hromada. Celé triedenie spočíva v tom, že si zo vstupného poľa vytvoríme binárnu hromadu a následne postupným vyberaním a mazaním všetkých jej prvkov toto pole utriedime.

Hromada, ktorú využíva algoritmus Heap Sort, musí spĺňať nasledovné podmienky (ak indexujeme pole od 0):

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

2. Pre ľubovoľný prvok (uzol), 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 hromady z poľa a zmazanie hromady.

Princíp algoritmu Heapify spočíva v tom, že ak máme i-ty prvok v poli (v kompletnom binárnom strome), ktorého potomkovia tvoria dve samostatné podhromady, potom tieto dve podhromady zlúčime 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 (podhromady).

Slovný opis algoritmu

Na vstupe prijmeme pole a index i, v ktorom chceme vytvoriť hromadu (Max Heap). Najskôr skontrolujeme, či prvok na indexe i má nejakých potomkov (využijeme rovnice (1) a (2) z časti "Prehľad"). Ak nemá žiadnych potomkov, funkcia skončí, pretože i predstavuje vrchol jednoprvkovej hromady. Ak má práve jedného potomka, tento potomok je zároveň jeho maximálnym potomkom. Ak má práve dvoch potomkov, tak porovnáme ich hodnoty a vyberieme z nich 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 želaná hromada už je utvorená. 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.

1.5. 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

Základné časti algoritmu

vytvorenie hromady
zmazanie hromady

Slovný opis

Vytvorenie hromady

Pri vytváraní hromady využijeme algoritmus heapify, pričom hromadu vytvoríme spôsobom zospodu na vrch. Najskôr si určíme prvok ktorý je najspodnejší a najviac vpravo a zároveň má aspoň jedného potomka. Tento prvok určíme veľmi jednoducho, pretože zpberieme posledný prvok v poli, a pomocou rovnice 3, ktorú si jemne upravíme mu nájdeme rodiča:

[math] \text{posledný rodič} = \left \lfloor \frac{\text{posledný index } - 1}{2} \right \rfloor = \left \lfloor\frac{\text{dĺžka } - 2}{2} \right \rfloor = \left \lfloor \frac{\text{dĺžka}}{2}\right \rfloor - 1 [/math]

Následne zavoláme Heapify na podhromadu s vrcholom posledného rodiča. Potom zmenšíme o 1 a opakujeme tento proces , až kým neprídeme na začiatok. Schematicky by sme to mohli napísať takto:

[math] \text{pre } i \text{ z intervalu } \left \langle \left \lfloor \frac {\text{dĺžka}}{2} \right \rfloor - 1 \quad ; \quad 0 \right \rangle :\ \text{heapify( pole[], dĺžka, i )}[/math]

Zmazanie hromady

Pri mazaní hromady vykonáme dve operácie. Ako prvé vymeníme prvok na vrchu hromady s koncovým prvkom hromady. Prvok čo je na komci považujeme za zmazaný, preto veľkosť hromady znížime o 1. Následne musíme zabezpečiť zachovanie pravidiel pre hromadu, takže zavoláme funkciu Heapify na celú hromadu (index i bude vrch hromady, čiže 0-tý prvok v poli). Tento proces opakujeme, poikiaľ v hromade neostanú žiadne prvky.

Poznámka: v našom prípade nemusíme mazať celú hromadu, ale iba do chvíle, keď nám neostane 1 prvok.

Schematicky by sme to mohli zapísať takto:

[math]\text{pre } j \text{ z intervalu } \left \langle \text{dĺžka - 1} \quad ; \quad 0 \right \rangle : \ \ \text{vymeň(pole[0], pole[$j$])} \ \ a \ \ \text{heapify(pole[], dĺžka, 0)} [/math]

Pseudokód

Nech funkcia Heap Sort má nasledovný prototyp: HeapSort(pole[], dlzka)

1. Nech: i = dlzka / 2 - 1, kde "/" predstavuje celočíslené delenie.

2. Je i >= 0 ? Ak áno, pokračuj krokom 2.1., inak skoč na krok 3.

2.1. Zavolaj funkciu Heapify(pole[], dlzka, i)

2.2. Skoč na krok 2.

3. Nech: j = dlzka - 1

4 Je j > 0 ? Ak áno, pokračuj krokom 4.1, inak skonči.

4.1. Vymeň: pole[0] a pole[j]

4.2. Zavolaj funkciu Heapify(pole[], dlzka, i)

4.3. Skoč na krok 4.

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

Iteračná CRekurzívna CRekurzívna Java

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

class HeapSortRE {
    void swap(int[] pole, int a, int b) {
        int tmp = pole[a];
        pole[a] = pole[b];
        pole[b] = tmp;
    }
    
    void heapify(int[] pole, int n, int i) {
        int max = i; // rodič
        int l = 2 * i + 1; // ľavý potomok
        int p = 2 * i + 2; // pravý potomok

        /* Ak je ľavý potomok väčší ako rodič */
        if (l < n && pole[l] > pole[max])
            max = l;

        /* Ak je pravý potomok väčší ako rodič */
        if (p < n && pole[p] > pole[max])
            max = p;

        /* Ak sa rodič v priebehu funkcie zmenil */
        if (max != i) {
            swap(pole, i, max);

            heapify(pole, n, max);
        }
    }

    public void sort(int[] pole) {
       int n = pole.length;

       /* Vytvorenie hromadu */
        for (int i = n / 2 - 1; i >= 0 ; i--)
            heapify(pole, n, i);

        /* Extrahovanie jednotlivých elemetov z hromady */
        for (int i = n - 1; i > 0; i--) {
            /* Presuň aktuálneho rodiča na koniec */
            swap(pole, 0, i);

            /* Zavolanie heapify na zredukovanú hromadu */
            heapify(pole, i, 0);
        }
    }
}

public class Main {

    static void printArray(int[] pole) {
        int n = pole.length;

        for (int i : pole)
            System.out.print(i + " ");

        System.out.println();
    }

    public static void main(String[] args) {
	    int[] pole = {12, 11, 13, 5, 6, 7};
	    int n = pole.length;

        System.out.println("Pole pred zoradenim: ");
        printArray(pole);

	    HeapSortRE hs = new HeapSortRE();
	    hs.sort(pole);

        System.out.println("Pole po zoradeni: ");
        printArray(pole);
    }
}

Selection Sort

Coming soon :)

Odkazy

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

Triedenie výberom: Rozdiel medzi revíziami

Verzia zo dňa a času 12:41, 10. apríl 2021

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

Základné časti algoritmu

Slovný opis

Vytvorenie hromady

Zmazanie hromady

Pseudokód

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