Halda je speciální druh binárního stromu, která se používá primárně pro efektivní nalezení minimálního (či maximálního) prvku v konstantním čase. Proto je to častá implementace prioritních front.

Aby byl nějaký binární strom haldou, musí každý jeho uzel splňovat tzv. vlastnost haldy, která říká, že klíč každého uzlu musí být větší nebo rovný klíčům oběma jeho potomkům (nebo menší nebo rovný v závislosti na směru řazení).

Základní operace haldy:

dequeueMinimum()
vrátí hodnotu prvku s minimálním klíčem a odebere jej
enqueue(key, value)
přidá prvek value s klíčem key
package ds.heap;

public interface Heap<T extends Comparable<? super T>> {
    void enqueue(T value);

    T dequeueMinimum();

    T peekMinimum();

    int size();
}

Zdrojový kód Pokrytí testy

Halda v poli

Haldu s n uzly lze uložit do pole o velikosti n tím způsobem, že kořen je uložen v jeho prvním prvku a pak pro něj a pro každý další uzel na indexu € i € platí, že jeho potomci se nachází na indexu € 2i+1 € a € 2i+2 €.

diagram

Oprava haldy

Operace pro opravu haldy zajišťuje, že vlastnost haldy platí pro všechny její prvky, a tedy na vrcholu zaručeně leží nejmenší (resp. největší) prvek. Oprava haldy se spouští ve dvou situacích: pokud odebíráme nejmenší (největší) prvek, a pokud vkládáme prvek nový.

  • při vkládání prvku se začne halda opravovat zdola nahoru a oprava začíná vloženým prvkem
  • při odebírání nejmenšího (největšího) prvku se halda začne opravovat shora dolu a oprava začíná kořenem celého stromu

Vytvoření haldy v poli

K vytvoření haldy v poli potřebujeme mít definovanou funkci pro opravu haldy (viz výše), kterou jen zavoláme pro všechny vnitřní uzly. Pro listy ji volat nemusíme, protože listy jsou samy o sobě triviálně haldami. Před opravou větších hald již musí být opraveny haldy menší, postupuje se tedy směrem od potomků k rodičům, tj. iterace přes pole začíná od konce pole a pokračuje směrem k jeho začátku.

Implementace

package ds.heap;

public class ArrayHeap<T extends Comparable<? super T>> implements Heap<T> {
    private final Comparable[] array;
    private int size;

    public ArrayHeap(final int maxSize) {
        this.array = new Comparable[maxSize];
        this.size = 0;
    }

    @Override
    public void enqueue(final T value) {
        if (size >= array.length) {
            throw new IllegalStateException("Heap is already full.");
        }

        // put element to the end of the array
        array[size] = value;
        // fix the heap starting from the last element added
        fixHeapBottomUp(size);
        // increment the heap size
        size++;
    }

    @Override
    public T dequeueMinimum() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty.");
        }

        // the least element is always in the front
        final T min = (T) array[0];
        // remove the first element
        array[0] = null;
        // take the last element and move it to the front
        swap(0, size - 1);
        // make heap smaller
        size--;
        // fix the heap again
        fixHeapTopToBottom(0);

        return min;
    }

    @Override
    public T peekMinimum() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty.");
        }

        return (T) array[0];
    }

    @Override
    public int size() {
        return size;
    }

    private void fixHeapBottomUp(final int fixingIndex) {
        if (fixingIndex != 0) {
            final int fixingIndexParent = parent(fixingIndex);

            if (array[fixingIndex].compareTo(array[fixingIndexParent]) < 0) {
                // invalid order (bigger element above smaller one) - fix it
                swap(fixingIndex, fixingIndexParent);
                // continue fixing from the parent
                fixHeapBottomUp(fixingIndexParent);
            }
        }
    }

    private void fixHeapTopToBottom(final int rootIndex) {
        final int left = leftChild(rootIndex);
        final int right = rightChild(rootIndex);

        // find smallest between three elements: root, left child, right child
        int smallestIndex = rootIndex;

        if (left < size && array[left].compareTo(array[smallestIndex]) < 0) {
            smallestIndex = left;
        }
        if (right < size && array[right].compareTo(array[smallestIndex]) < 0) {
            smallestIndex = right;
        }

        if (smallestIndex != rootIndex) {
            // root was not the smallest, so swap it
            swap(rootIndex, smallestIndex);
            // and continue fixing the heap further down
            fixHeapTopToBottom(smallestIndex);
        }
    }

    // UTILITIES

    private int parent(final int pos) {
        return pos / 2;
    }

    private int leftChild(final int pos) {
        return (2 * pos);
    }

    private int rightChild(final int pos) {
        return (2 * pos) + 1;
    }

    private void swap(final int i1, final int i2) {
        final T backup = (T) array[i1];
        array[i1] = array[i2];
        array[i2] = backup;
    }
}

Zdrojový kód Pokrytí testy

Řazení

Výše uvedené metody lze využít k vytvoření řadícího algoritmu, který se nazývá heap sort. Funguje na principu postupného odebírání maximálních prvků z haldy.

package sort;

public class HeapSort {
    /**
     * Implementace algoritmu heap sort.
     * @param input pole k seřazení
     * @param ascending TRUE pro vzestupné řazení, FALSE pro sestupné
     */
    public static <T extends Comparable<? super T>> void heapSort(final T[] input, final boolean ascending) {
        // požadovaný směr řazení

        final int dir = ascending ? -1 : 1;

        // inicializovat haldu ve vstupním poli

        for (int i = (input.length / 2) - 1; i >= 0; i--) {
            HeapSort.sift(input, i, input.length - 1, dir);
        }

        // seřadit pole postupným posunem prvků na správné místo

        for (int i = input.length - 1; i > 0; i--) {
            // vložit prvek "i" na vrchol
            HeapSort.swap(input, i, 0);
            // prosít prvek na správé místo
            HeapSort.sift(input, 0, i - 1, dir);
        }
    }

    /**
     * Metoda pro opravu haldy - umístí zvolený prvek na správné místo.
     * @param input pole k seřazení
     * @param iTop index vrcholu haldy
     * @param iBottom poslední index haldy
     * @param dir směr řazení (-1 vzestupně, +1 sestupně)
     */
    private static <T extends Comparable<? super T>> void sift(final T[] input, final int iTop, final int iBottom, final int dir) {
        int iRoot = iTop;
        int iChild = (iRoot * 2) + 1;

        while (iChild <= iBottom) {
            // vyhledat místo pro vložení hodnoty

            if ((iChild < iBottom) && (input[iChild].compareTo(input[iChild + 1]) == dir)) {
                iChild++;
            }

            if (input[iRoot].compareTo(input[iChild]) == dir) {
                // prohodit oba prvky
                HeapSort.swap(input, iRoot, iChild);
                // pokračovat v prosívání od potomka
                iRoot = iChild;
                iChild = (iRoot * 2) + 1;
                continue;
            }

            // ukončit prosívání
            break;
        }
    }

    /**
     * Metoda pro prohození dvou prvků.
     * @param input vstupní pole
     * @param i1 první index
     * @param i2 druhý index
     */
    private static <T extends Comparable<? super T>> void swap(final T[] input, final int i1, final int i2) {
        final T temp = input[i2];
        input[i2] = input[i1];
        input[i1] = temp;
    }
}

Zdrojový kód Pokrytí testy

Reference