Binomiální halda
Binomiální halda obsahující binomiální stromy řádu 0, 1, 2, 3 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

 /**
  * 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;
         }
     }
 }
 







Doporučujeme