Binární halda

Hodnoty uložené v binární haldě (min-heap)

Binární halda (binary heap) je úplný binární strom, ve kterém platí, že každý potomek vrcholku má nižší nebo stejnou hodnotu nežli vrcholek sám. V případě, že není poslední hladina haldy zaplněna, jsou uzly ukládány do haldy zleva.

Další důležitou vlastností je, že pokud indexujeme (od čísla 1) prvky haldy od shora dolů, zleva doprava, pak potomci každého vrcholu jsou na indexu a 2i + 1 , tato vlastnost je zajištěna tím, že v haldě nevynecháváme mezery. Graficky si tedy haldu můžeme představit jako pyramidu s useknutou základnou.

Vlastnost býti haldou je rekurzivní - všechny podstromy haldy jsou také haldy. Díky této vlastnosti máme zajištěno, že se halda chová jako prioritní fronta - na vrcholek haldy vždy musí vystoupit prvek s nejvyšší prioritou (čehož se využívá u heapsortu – řazení haldou).

V případě, že považujeme za vyšší prioritu nižší hodnotu klíče, hovoříme o min-heap, při opačném uspořádání o max-heap.

Operace

Repair top

Mějme haldu, u níž víme, že její vrchol nerespektuje uspořádání. Pomocná procedura repairTop přesune tento vrchol na odpovídající pozici, čímž obnoví požadované vlastnosti haldy. Samotná implementace je jednoduchá – algoritmus porovnává uzel otce s jeho syny, pokud má některý ze synů vyšší prioritu, tak jej prohodí s otcem, pokud mají oba synové vyšší prioritu, tak prohodí otce se synem s nejvyšší prioritou. Algoritmus dále iterativně pokračuje o úroveň níže, dokud buď nenarazí na nejspodnější úroveň haldy, nebo dokud není priorita otce vyšší než obou jeho synů (vlastnost býti haldou je obnovena).

Asymptotická složitost procedury repairTop je $O(\\log_{2}{n})$ , protože halda má maximálně logaritmickou hloubku.

Heapify

Pomocná procedura heapify zkonstruuje v zadaném poli haldu. Jelikož je vlastnost býti haldou rekurzivní, tak pro konstrukci haldy musíme opravit všechny její netriviální podhaldy. Postupujeme proto po vrcholech všech netriviálních podhald (indexy $n/2 \\rightarrow 1$ ) a voláme operaci repairTop. Po ukončení výše zmíněné smyčky zadané pole reprezentuje haldu. Asymptotická složitost procedury heapify je O(n) .

Insert

Operace vkládání (insert) funguje přesně naopak než operace repairTop. Nový prvek je přidán na konec haldy a probublává vzhůru tak dlouho, dokud má vyšší prioritu než jeho otec. Asymptotická složitost vkládání je $O(\\log_{2}{n})$ .

Top

Operace top vrátí hodnotu prvku s nejvyšší prioritou – tj. vrcholu. Jelikož se jedná o návrat prvního prvku pole, tak má operace top konstantní asymptotickou složitost O(1) .

Return top

Operace returnTop vrátí prvek s nejvyšší prioritou a odstraní jej z haldy. Samotné smazání provede tak, že vrchol haldy nahradí jejím posledním prvkem, zkrátí haldu o 1 (dekrementuje proměnnou reprezentující prvků haldy) a zavolá operaci repairTop na vrchol haldy. Asymptotická složitost operace returnTop je totožná se složitostí volání repairTop – $O(\\log_{2}{n})$ .

Merge

Operace merge sloučí dvě haldy do jedné – vytvoří nové pole, do nějž nakopíruje obsah obou hald a na toto nové pole zavolá operaci heapify. Asymptotická složitost tohoto postupu je O(m+n) , kde je velikost první haldy a je velikost druhé haldy.

Kód

Java

/**
 * Binarni halda (min-heap)
 * @author Pavel Micka
 */
public class BinaryHeap {
 
    private int[] array;
    private int size; //velikost haldy...je treba mit na pameti, ze indexujeme od 1
 
    /**
     * Konstruktor
     * @param arraySize velikost haldy
     */
    public BinaryHeap(int arraySize) {
        this.array = new int[arraySize + 1]; //na prvnim miste nebude nic
        this.size = 0;
    }
 
    /**
     * Konstruktor
     * @param arraySize velikost haldy
     */
    public BinaryHeap(int[] source) {
        this.array = new int[source.length + 1]; //na prvnim miste nebude nic
        System.arraycopy(source, 0, array, 1, source.length);
        this.size = 0;
    }
 
    /**
     * Provede operaci slouceni hald
     * @param heap halda, ktera bude sloucena s touto haldou
     */
    public void merge(BinaryHeap heap) {
        int[] newArray = new int[this.size + heap.size + 1];
 
        System.arraycopy(array, 1, newArray, 1, this.size);
        System.arraycopy(heap.array, 1, newArray, this.size + 1, heap.size);
 
        size = this.size + heap.size;
        array = newArray;
        heapify(newArray);
    }
 
    /**
     * Vrati pole vsech prvku v halde
     * @return pole vsech prvku v halde
     */
    public int[] getAll() {
        return Arrays.copyOfRange(array, 1, this.size + 1);
    }
 
    /**
     * Vlozi prvek do haldy
     * @param i prvek k vlozeni
     */
    public void insert(int i) {
        size++;
        int index = this.size;
        while (i < array[index / 2] && index != 0) { //dokud je nas prvek mensi nez jeho otec
            array[index] = array[index / 2]; //pak otce posuneme o uroven niz (cimz se nam mezera na vlozeni posune o patro)
            index /= 2; //a opakujeme o uroven vys
        }
        array[index] = i; //o patro vys je jiz prvek nizsi, proto vlozime prvek prave sem, vlastnost haldy byla obnovena
    }
 
    public int top() {
        if (getSize() == 0) {
            throw new IllegalStateException("halda je prazdna");
        }
        return array[1];
    }
 
    /**
     * Odstrani vrchol a vrati ho
     * @return vraceny vrchol
     */
    public int returnTop() {
        if (getSize() == 0) {
            throw new IllegalStateException("halda je prazdna");
        }
        int tmp = array[1];
        array[1] = array[this.size];
        size--;
        repairTop(this.size, 1);
        return tmp;
    }
 
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 1; i <= this.size; i++) {
            builder.append(array[i]).append(" ");
        }
        return builder.toString();
    }
 
    /**
     * @return the size
     */
    public int getSize() {
        return size;
    }
     
    /**
     * Vytvor haldu ze zdrojoveho pole
     * @param array pole
     */
    private void heapify(int[] array) {
        for (int i = array.length / 2; i > 0; i--) {
            repairTop(this.size, i);
        }
    }
     
    /**
     * Umisti vrchol haldy na korektni misto v halde (opravi haldu)
     * @param bottom posledni index pole, na ktery se jeste smi sahnout
     * @param topIndex index vrsku haldy
     */
    private void repairTop(int bottom, int topIndex) {
        int tmp = array[topIndex];
        int succ = topIndex * 2;
        if (succ < bottom && array[succ] > array[succ + 1]) {
            succ++;
        }
 
        while (succ <= bottom && tmp > array[succ]) {
            array[topIndex] = array[succ];
            topIndex = succ;
            succ = succ * 2;
            if (succ < bottom && array[succ] > array[succ + 1]) {
                succ++;
            }
        }
        array[topIndex] = tmp;
    }    
}