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