Heap sort – triedenie haldou v Java

Triediace algoritmy sa používajú na vzostupné alebo zostupné preusporiadanie prvkov poľa alebo zoznamu podľa numerického či lexikografického poradia. Triedenie je veľmi dôležité pre optimálny výkon iných algoritmov, ktoré vyžadujú triedené vstupné dáta.

Existuje množstvo rozličných triediacich algoritmov. Výber vhodného algoritmu závisí na faktoroch ako veľkosť a vlastnosti vstupných dát, dostupná pamäť a požiadavky na časovú a priestorovú náročnosť.

Aby sme ti uľahčili výber, predstavíme si v našom seriáli postupne najznámejšie algoritmy triedenia dát, vysvetlíme si ich princípy, výhody a nevýhody a naprogramujeme si ich v Jave.

Doteraz sme sa venovali nasledujúcim triediacim algoritmom:

• Triediace algoritmy – úvod do triedenia dát,
• Bubble sort – bublinkové triedenie,
• Comb sort – hrebeňové triedenie,
• Big O notácia– analýza zložitosti algoritmov,
• Selection sort – triedenie výberom,
• Insertion sort – triedenie vkladaním,
• Counting sort – triedenie počítaním.

Dnes sa budeme venovať triedeniu pomocou dátovej štruktúry halda (angl. heap sort).

Heap sort

Heapsort, ktorý vytvoril J. W. J. Williams v roku 1964, je pomerne populárny a veľmi efektívny triediaci algoritmus, ktorý si vstupné dáta ukladá do dátovej štruktúry nazývanej halda (heap). Halda je úplný binárny strom (complete binary tree). Má veľmi zaujímavú vlastnosť, ktorú môžeme použiť na nájdenie rodičov a potomkov ktoréhokoľvek uzla v strome. Je to dané tým, ako sa skonštruuje halda zo vstupného poľa.  Ak je index ľubovoľného prvku v poli i, potom platí, že ľavý potomok bude mať index 2*i+1 a pravý 2*i+2. Rodič akéhokoľvek prvku pre index i je daný spodnou hranicou (i-1)/2. Koreňový uzol stromu ma index 0. Práve vďaka tejto indexovej aritmetike sa dá vstupné pole dá namapovať na úplný binárny strom (haldu) a nie je potrebné alokovať dodatočnú pamäť.

Špeciálnymi formami haldy sú tzv. Max-Heap a Min-Heap a práve tieto formy sa využívajú v triedení heap-sort. V halde Max-Heap platí, že hodnota v každom rodičovskom uzle je väčšia ako je jeho priamych (1 úroveň nižšie) a nepriamych (2 a viac úrovní pod rodičom) potomkov. V Min-Heap je hodnota rodičovského uzla menšia ako jeho potomkov. Pre vzostupné preusporiadanie prvkov využijeme Max-Heap, kde v koreňovom uzle bude maximálna hodnota stromu a pre zostupné Min-Heap s najmenšou hodnotou v koreňovom uzle.

Heap sort algoritmus  – princíp fungovania

V prvom kroku vytvoríme zo vstupného vektora prvkov haldu. Tú transformujeme na Max-Heap formu, vytvoríme si na to metódu heapify. Tá bude rekurzívne porovnávať rodičov a jeho potomkov a vymieňať hodnoty, aby sa zabezpečilo presunutie prvku s najvyššou hodnotou do koreňu stromu. Tá sa potom vymení s posledným listom v strome a tento list (s maximálnou hodnotou) sa ustrihne. Tento prvok sa považuje za zotriedený a veľkosť haldy sa zmenší o 1. Tým, že sa vymenil koreňový uzol, halda stratila svoju Max-Heap podobu a budeme musieť zopakovať celý postup. Postupne ako zostrihávame zo stromu aktuálne najvyššie hodnoty, vykonávame triedenie. Triedenie sa skončí, keď nám v halde ostane iba jeden prvok, ktorý je najmenší a patrí na začiatok poľa.

Výhody algoritmu Heap sort

• Stabilná časová zložitosť O(n log n) vo všetkých prípadoch,
• nevyžaduje dodatočnú pamäť,
• výkon algoritmu neklesá s množstvom vstupných dát.

Nevýhody algoritmu Heap sort

• Nevhodný pre malé množstvo prvkov, prejaví sa réžia na vytváranie a presúvanie prvkov v halde,
• nie je stabilný,
• nie je adaptabilný.

Heap sort časová náročnosť

Heap sort animácie, vizualizácia, gif

Vizualizácia heap sort vyzerá nasledovne:

Zdroj: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms

Animáciu algoritmu nájdeš napríklad na stránke Toptal. Nachádza sa tam 8 typov algoritmov, animáciu si môžeš pustiť aj pozadu.

Na tejto stránke si môžeš prejsť jednotlivými krokmi algoritmu, vďaka čomu si vieš overiť časovú náročnosť algoritmu.

Heap Sort Implementácia, Java kód

Teraz si ukážeme implementáciu algoritmu Heap sort v Jave.

HeapSort.java

package sorting;

public class HeapSort {
    public void sort(int data[])
    {
        // Don't sort if there are no elements
        if(data.length == 0)
            return;

        // Build Max-Heap by rearranging array
        for (int i = data.length / 2 - 1; i >= 0; i--) {
            heapify(data, data.length, i);
        }

        // Extract max element from the heap one by one
        for (int i = data.length - 1; i > 0; i--) {
            int temp = data[0];
            data[0] = data[i];
            data[i] = temp;
            System.out.print("max-heap root node extraction: " + data[i] + " -> ");
            printArray(data);
            System.out.println("");
            // Heapify root node
            heapify(data, i, 0);
        }
    }

    // Heapify the subtree by the index i, where n is size of the heap
    void heapify(int data[], int n, int i) {
        System.out.print("heapify (" + n + ", " + i + ") on ");
        printArray(data);
        // Find max of (root, left child, right child)
        int max = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && data[left] > data[max])
            max = left;

        if (right < n && data[right] > data[max])
            max = right;

        // Swap and continue heapifying if root is not max
        if (max != i) {
            int swap = data[i];
            data[i] = data[max];
            data[max] = swap;
            System.out.println(" => exchange " + data[max] + " for " + data[i]);
            heapify(data, n, max);
        }
        else {
            System.out.println(" => no change");
        }
    }

    // Function to print an array
    public void printArray(int data[])
    {
        for (int i = 0; i < data.length; i++)
            System.out.print(data[i] + " ");
        //System.out.println();
    }
}

Main.java

import sorting.HeapSort;

public class Main {
    public static void main(String[] args) {
        int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
        HeapSort heapSort = new HeapSort();
        System.out.print("Input: ");
        heapSort.printArray(dataToSort);
        System.out.println("");
        heapSort.sort(dataToSort);
        System.out.print("Sorted: ");
        heapSort.printArray(dataToSort);
    }
}

Výstup z tohto príkladu je:

Pripravili sme pre teba súbory so spomínaným príkladom vo forme kódu, ktorý si môžeš spustiť priamo v Jave. Stiahni si Java Heap Sort kód.

Ak si Java programátor a hľadáš prácu, pozri si naše benefity pre zamestnancov a reaguj na najnovšie ponuky práce.

O autorovi

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.