D-regulární halda

D-regulární halda je n-ární úplný strom (zaplňovaný zleva doprava), ve kterém platí, že každý předek má nižší hodnotu (prioritu) než všichni jeho potomci. Tento typ uspořádání haldy se nazývá min heap, v případě opačného uspořádání hovoříme o max heap. Speciálním případem d-regulární haldy pro d = 2 je binární halda. D-regulární halda funguje díky svým vlastnostem jako prioritní fronta.

Implementace

Za předpokladu, že implemetujeme haldu pomocí pole indexovaného od 0, tak nalezneme předka prvku na indexu (k-1)/d . Potomky tohoto prvku nalezneme na indexech $d \\cdot k + 1, \\cdots ,\\, d \\cdot k + d$ . Je vhodné, aby bylo mocninou čísla 2, protože pak můžeme nahradit operace násobení a dělení bitovými posuvy.

Kód

Java

/**
 * D-regularni halda (d-ary heap)
 * Implementovana jako min-heap
 * @author Pavel Micka
 */
public class DAryHeap<ENTITY extends Comparable> {
 
    private final static int EXPAND_RATIO = 2; //kolikrat bude pole hodnot zvetseno pri expanzi
    private final static double COLLAPSE_RATIO = 0.25; //pomer pri nemz bude pole hodnot kontrahovano
    private Object[] array;
    private int d; //parametr d (arita)
    private int size; //velikost haldy
    private int initialSize;
 
    /**
     * Konstruktor
     * @param arraySize inicialni kapacita haldy
     */
    public DAryHeap(int initialSize, int d) {
        if (d < 2) {
            throw new IllegalArgumentException("D must be at least 2.");
        }
        this.d = d;
        this.array = new Object[initialSize];
        this.initialSize = initialSize;
        this.size = 0;
    } 
 
    /**
     * Vlozi prvek do haldy
     * Slozitost: O(log(n))
     * @param i prvek, ktery bude vlozen
     */
    public void insert(ENTITY i) {
        if (array.length == size) {
            expand();
        }
        size++;
        int index = size - 1;
        int parentIndex = getParentIndex(index);
        while (index != 0 && i.compareTo(array[parentIndex]) < 0) { //pokud je prvek mensi nez jeho otec
            array[index] = array[parentIndex]; //posun otce o uroven nize
            index = parentIndex; //opakuj proceduru na dalsi urovni
            parentIndex = getParentIndex(index);
        }
        array[index] = i; //umisti prvek na prislusnou pozici
    }
 
    /**
     * Vrati a odstrani prvek na vrchu haldy
     * Slozitost: O(log(n))
     * @return prvek na vrchu haldy
     */
    public ENTITY returnTop() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        ENTITY tmp = (ENTITY) array[0];
        array[0] = array[size - 1];
        size--;
        if (size < array.length * COLLAPSE_RATIO && array.length / EXPAND_RATIO > initialSize) {
            collapse();
        }
        repairTop(0);
        return tmp;
    }
 
    /**
     * Slouci danou haldu do teto haldy
     * Slozitost: O(n)
     * @param heap halda, jez bude sloucena do teto haldy
     */
    public void merge(DAryHeap<ENTITY> heap) {
        Object[] newArray = new Object[array.length + heap.array.length];
        System.arraycopy(array, 0, newArray, 0, size);
        System.arraycopy(heap.array, 0, newArray, size, heap.size);
        size = size + heap.size;
        array = newArray;
        //build heap
        for (int i = newArray.length / d; i >= 0; i--) {
            repairTop(i);
        }
    }
 
    /**
     * Vrat index rodicovskeho uzlu stromu
     * @param index index prvku, pro nejz bude vyhledan rodic
     * @return index rodicovskeho uzlu stromu
     */
    private int getParentIndex(int index) {
        return (index - 1) / d;
    }
 
    /**
     * Umisti vrchol haldy na spravne misto v halde (tj. opravi vlasnost haldy usporadani) 
     * @param topIndex index vrcholu haldy
     */
    private void repairTop(int topIndex) {
        Comparable tmp = (Comparable) array[topIndex];
        int succ = findSuccessor(topIndex * d + 1, topIndex * d + d);
        while (succ < size && tmp.compareTo(array[succ]) > 0) {
            array[topIndex] = array[succ];
            topIndex = succ;
            succ = findSuccessor(succ * d + 1, succ * d + d);
        }
        array[topIndex] = tmp;
    }
 
    /**
     * Vrati index potomka s nejnizsi hodnotou
     * @param from index prvniho potomka
     * @param to index posledniho potomka
     * @return index index potomka s nejnizsi hodnotou
     */
    private int findSuccessor(int from, int to) {
        int succ = from;
        for (int i = from + 1; i <= to && i < size; i++) {
            if (((Comparable) array[succ]).compareTo((Comparable) array[i]) > 0) {
                succ = i;
            }
        }
        return succ;
    }
 
    /**
     * Expanduje pole hodnot
     */
    private void expand() {
        array = Arrays.copyOf(array, array.length * EXPAND_RATIO);
    }
 
    /**
     * Kontraguje pole hodnot
     */
    private void collapse() {
        array = Arrays.copyOf(array, array.length / EXPAND_RATIO);
    }
 
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < size; i++) {
            builder.append(array[i]).append(" ");
        }
        return builder.toString();
    }
}

Implementace

Kód

Doporučujeme