Řazení haldou

(c) RolandH, CC-BY-SA-3.0

Řazení haldou v akci na několika náhodných číslech. Před samotným řazením je nastíněna stromová struktura.

Ukázka práce algoritmu s využitím haldy

Řazení haldou je jeden z nejlepších obecných algoritmů řazení, založených na porovnávání prvků. Byť je v průměru o něco pomalejší než dobře napsaný algoritmus rychlého řazení, je jeho zaručená časová náročnost ${\displaystyle O(N\log {N})}$. a dokáže řadit data na původním místě (má pouze konstantní nároky na paměť). Řazení haldou není stabilní řadicí algoritmus.

Popis algoritmu

Základní myšlenkou tohoto algoritmu je využití datové struktury označované jako halda. Tato struktura umí velmi efektivně provést operaci vložení prvku a operaci výběr největšího prvku. Proto lze pomocí haldy seřadit dodaná data od největšího k nejmenšímu prostě pomocí jejich vložení do haldy a následného postupného vybírání největšího prvku.

Algoritmus funguje s libovolnou implementací haldy. Při řazení prvků v poli lze využít následující implementaci haldy v poli, která dovoluje třídit prvky na místě.

V praxi lze haldu vystavět přímo ve vstupním poli tím způsobem, že jsou následovníci prvku n uloženi do prvků 2n a 2n+1 (při indexování od jedničky), a také následné vybírání prvků lze provádět pouhým přeuspořádáváním dat v tomto poli.

Pomocný algoritmus

Uvažujme binární haldu pro nalezení „nejvyššího“ prvku. Tato halda bude umístěna v poli od indexu 1 do indexu N. „Pravidlem haldy“ je, že prvek umístěný na indexu i je vyšší než prvky umístěné na indexech 2*i a 2*i+1. U koncových uzlů (na indexech N/2+1 až N) je „pravidlo haldy“ automaticky splněné - není je s čím porovnávat.

Pro oba kroky řazení je využit pomocný algoritmus, který v čase O(log(n)) dokáže prodloužit částečně vytvořenou haldu zepředu o jeden prvek. Přesněji řečeno - pokud všechny prvky s indexy L+1 až R (včetně krajních prvků) splňují „pravidlo haldy“, po provedení pomocného algoritmu budou splňovat pravidlo haldy prvky s indexy L až R. Pokud prvek na indexu L nevyhovuje pravidlu haldy, vyměníme ho s větším z prvků na indexech 2*L a 2*L+1 a postup zopakujeme pro index, s kterým jsme měnili.

Stavba haldy

První krok haldového řazení spočívá v postupném prodlužování haldy z rozsahu (N/2 až N) na (1 až N). Po provedení N/2 kroků je halda vytvořena.

Využití haldy

Halda, která splňuje popsané podmínky, má na vrcholu (index 1) prvek s největší hodnotou. Ve druhém kroku haldového řazení se tento prvek vymění za poslední prvek pole. Tak se na konec pole dostane největší prvek (tím je zařazen na správné místo), ale změnou prvku v kořeni haldy dojde k porušení jejího pravidla. Je třeba spustit pomocný algoritmus pro zatřídění vyměněného prvku na indexu 1 do haldy, aby tentokrát vznikla halda pro prvky s indexy (1 až N-1).

Výše zmíněný postup se opakuje pro stále se zmenšující haldu. Při každém kroku je na vrcholu haldy největší ze zbývajících prvků, a ten je výměnou s posledním prvkem této menší haldy zařazen na správné pořadí v poli.

Kód algoritmu v jazyce C

/* Makra pro index levého potomka, pravého potomka a rodiče */
#define LEFT(i) (2*(i)+1)
#define RIGHT(i) (2*(i)+2)
#define PARENT(i) (((i)-1)/2)

void razeni_haldou (double array[], int n) {
    int z; /* Halda tvoří prvky s indexy 0..(z-1) */
    int i;
    double temp;

    /*
    ** Vytvoření haldy
    ** Jednoprvkové pole (array[0]) je vždy halda;
    ** postupně přidáváme array[1], array[2], ... a opravujeme haldu
    */
    for (z = 1; z < n; z++) {
        temp = array[z];
        i = z;
        /* Bublání přidaného prvku nahoru */
        while (i > 0 && temp > array[PARENT(i)]) {
            array[i] = array[PARENT(i)];
            i = PARENT(i);
        }
        array[i] = temp;
    }
    /*
    ** Vlastní třídění
    ** setříděný úsek je od indexu z+1 (na začátku prázdný)
    ** array[0] je největší prvek; vyhodíme ho za haldu - na pozici array[z]
    ** Prvek array[z] přemístíme do array[0] a obnovíme haldu.
    */
    for (z = n - 1; z > 0; z--) {
        temp = array[z]; /* Poslední prvek zkusím umístit do kořene a bublat dolů */
        array[z] = array[0]; /* Největší prvek do setříděné části za haldu */
        i = 0;
        /* Je-li některý z potomků větší, je třeba bublat dolů */
        while ((LEFT(i) < z && array[LEFT(i)] > temp) ||
                    (RIGHT(i) < z && array[RIGHT(i)] > temp)) {
            /* Který z potomků je větší? */
            /* Prvek má oba potomky, pokud RIGHT(i)<z. */
            if (RIGHT(i) < z && array[LEFT(i)] < array[RIGHT(i)]) {
                /* Pravý potomek je větší, dám ho do rodiče */
                array[i] = array[RIGHT(i)];
                i = RIGHT(i);
            } else {
                /* Pravý potomek neexistuje, nebo levý je větší */
                array[i] = array[LEFT(i)];
                i = LEFT(i);
            }
        }
        array[i] = temp; /* Sem patří prvek z pozice array[z] */
    }
}

Externí odkazy

• Obrázky, zvuky či videa k tématu řazení haldou na Wikimedia Commons