Binomiální halda

Binomiální halda (Binomial heap) je halda složená z lesa binomiálních stromů. Každý prvek každého stromu má vyšší prioritu, než kterýkoliv z jeho potomků – halda se proto chová jako prioritní fronta. Binomiální halda má oproti binární a d-regulární haldě výhodu v rychlejších operacích sloučení hald ( $O(\\log n)$ ) a vložení prvku (amortizovaně O(1) ).

Binomiální strom

Binonomiální strom řádu 0 obsahuje právě jeden uzel. Binomiální strom řádu n vznikne sloučením dvou stromů řádu n-1 takovým způsobem, že porovnáme prioritu kořenů obou stromů a následně ten s nižší prioritou zavěsíme pod kořen s vyšší prioritou. Binomiální halda obsahuje maximálně jeden strom každého řádu.

Binomiální strom řádu n obsahuje $2^{n}$ uzlů.
Binomiální strom řádu n má hloubku n.
Kořen binomiální stromu má n potomků.
Kořen binomiálního stromu obsahuje jako své potomky všechny stromy nižších řádů.

Základní operace binomiální haldy

Operace jsou popsány pro min-heap – nižší prvek má vyšší prioritu. Max-heap (tj. vyšší prvek má vyšši prioritu) funguje analogicky.

Insert

Vloží prvek do haldy. Vytvoří pro prvek binomiální strom řádu 0 a provede sloučení tohoto stromu s haldou. Pokud vkládáme prvek s nižší prioritou, než je priorita současného nejnižšího prvku haldy, tak tento prvek označíme za minimální. Asymptotická složitost operace je $O(\\log n)$ , amortizovaná složitost O(1) .

Return top

Vrátí a smaže z haldy prvek s nejvyšší prioritou. Odebere minimální prvek haldy, všechny podstromy přidá zpět do haldy prostřednictvím operace merge. Nalezne nový nejnižší prvek průchodem přes všechny kořeny binomiálních stromů. Asymptotická složitost operace je $O(\\log n)$ .

Merge

Provede sloučení haldy B do haldy A. Tato operace odpovídá sčítání dvou binárních čísel. Algoritmus prochází obě haldy od nejnižšího řádu, pokud halda B obsahuje strom řádu n a halda A nikoliv, pak jej pouze překopíruje. Pokud obě haldy obsahují stromy stejného řádu, tak je sloučí do přenosového stromu (obdoba přenosového bitu u sčítání), který zohlední pří následném spojování stromů řádu n+1 . Nakonec porovná minimální prvky obou slučovaných hald a za minimální prvek výsledné haldy označí nižší z nich. Asymptotická složitost operace je $O(\\log n)$ .

Kód

Java

/**
 * Binomialni halda
 * Radi prvky dle priority (mensi == vyssi priorita)
 * @author Pavel Micka
 */
public class BinomialHeap<ENTITY extends Comparable> {
    private Node<ENTITY>[] nodes;
    private Node<ENTITY> min;
    /**
     * Konstruktor
     * @param capacity kapacita haldy
     */
    public BinomialHeap(int capacity) {
        min = null;
        nodes = new Node[((int) (Math.log(capacity) / Math.log(2))) + 2];
    }
 
    /**
     * Vlozi prvek do haldy, pokud je mensi nez aktualni minimalni, tak
     * jej ulozi jako nejmensi prvek
     * @param e
     */
    public void insert(ENTITY e) {
        Node<ENTITY> n = new Node<ENTITY>(e);
        if (nodes[0] != null) merge(n, nodes[0]);
        else nodes[0] = n;
 
        if (min == null) min = n;
        else if (min.value.compareTo(n.value) == 1) min = n;
    }
 
    /**
     * Smaze a vrati entitu s nejvyssi prioritou
     * @return entita s nejvyssi prioritou, @null, pokud je halda prazdna
     */
    public ENTITY returnTop() {
        if(min == null) return null;
        ENTITY tmp = min.value;
        nodes[min.order] = null; //strom vyjmeme
        for (Node n : min.children) { //a z potomku udelame nove stromu
            n.parent = null;
            if(nodes[n.order] != null) merge(n, nodes[n.order]);
            else nodes[n.order] = n;
        }
        min.children.clear();
        ENTITY minVal = null;
        Node minNode = null;
        for(int i = 0; i < nodes.length; i++){
            if(nodes[i] != null){
                if(minVal == null){
                    minVal = nodes[i].value;
                    minNode = nodes[i];
                }
                else if(minVal.compareTo(nodes[i].value) == 1){
                    minVal = nodes[i].value;
                    minNode = nodes[i];
                }
            }
        }
        min = minNode;
        return tmp;
    }
 
    /**
     * Slouci haldy, pokud mergovana halda obsahuje mensi prvek, nez halda, na
     * ktere je volana operace, pak je tento prvek minimalni i ve sloucene halde
     * @param heap
     */
    public void mergeHeaps(BinomialHeap<ENTITY> heap) {
        Node<ENTITY> carry = null;
        for (int i = 0; i < heap.nodes.length; i++) {
            if(nodes[i] == null){
                if(heap.nodes[i] == null){
                    nodes[i] = carry;
                    carry = null;
                }else{
                    if(carry == null){
                        nodes[i] = heap.nodes[i];
                    }else{
                        carry = mergeTrees(heap.nodes[i], carry);
                    }
                }
            }else{
                if(heap.nodes[i] == null){
                    if(carry != null){
                        carry = mergeTrees(nodes[i], carry);
                        nodes[i] = null;
                    }
                }else{
                    if(carry == null){
                        carry = mergeTrees(nodes[i], heap.nodes[i]);
                        nodes[i] = null;
                    }else{
                        carry = mergeTrees(carry, heap.nodes[i]);
                    }
                }
            }
        }
 
        if(carry != null) throw new RuntimeException("Preteceni haldy (halda je preplnena)");
 
        if (this.min == null) this.min = heap.min;
        else if(this.min != null && heap.min != null && heap.min.value.compareTo(min.value) == -1) min = heap.min;
    }
 
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for(int i = 0; i < nodes.length; i++){
            if(nodes[i] == null) builder.append(i + ": null\\n");
            else builder.append(i + ":\\n" + nodes[i].toString() + "\\n");
        }
        return builder.toString();
    }
     
    /**
     * Provede slouceni binomialnich stromu (vcetne preteceni do vyssich radu)
     * @param a
     * @param b
     */
    private void merge(Node a, Node b) {
        if (a.order != b.order)
            throw new IllegalArgumentException("Stromy nejsou stejneho radu");
        int tmpOrder = a.order;
        nodes[tmpOrder] = null;
        Node newRoot = null;
        newRoot = mergeTrees(a, b);
        if (nodes[tmpOrder + 1] == null) nodes[tmpOrder + 1] = newRoot;
        else merge(newRoot, nodes[tmpOrder + 1]);
    }
 
    /**
     * Slouci binomialni stromy v jeden (zavesi strom s nizsi prioritou pod strom
     * s vyssi prioritou)
     * @param a strom a
     * @param b strom b
     * @return
     */
    private Node mergeTrees(Node a, Node b) {
        Node newRoot = null;
        if (a.value.compareTo(b.value) < 0) {
            b.parent = a;
            a.children.add(b);
            a.order++;
            newRoot = a;
        } else {
            a.parent = b;
            b.children.add(a);
            b.order++;
            newRoot = b;
        }
        return newRoot;
    }
 
    /**
     * Reprezentuje uzel binomialni haldy
     * @param <ENTITY>
     */
    private class Node<ENTITY extends Comparable> {
        Node<ENTITY> parent;
        ENTITY value;
        List<Node> children;
        int order; //rad binomialni haldy
 
        public Node(ENTITY value) {
            this.value = value;
            children = new ArrayList<Node>();
            order = 0;
        }
 
        @Override
        public String toString() {
            String s = "Node value: " + value + ", order: " + order + "\\n";
            for(Node n : children){
                s += n.toString();
            }
            return s;
        }
    }
}

Binomiální strom

Základní operace binomiální haldy

Insert

Return top

Merge

Kód

Doporučujeme