src/main/java/de/dfki/lt/loot/jada/FibonacciHeapBase.java
public void removeMinimum() {  // Fibonacci-Heap-Extract-Min, CONSOLIDATE
   if (rootWithMinKey == null)
     throw new EmptyHeapException("trying to remove from an empty heap");

   if (debug) System.out.println("removeMinimum");
   --count;

   /// Phase 1: Make all the removed root's children new roots:
   // Make all children of root new roots:
   if (rootWithMinKey.child != null) {
     if (debugRemoveMin) {
       System.out.println("root's children: " +
                          rootWithMinKey.child.printAll());
     }
     HeapNode<Data> c = rootWithMinKey.child;
     do {
       c.parent = null;
       c = c.next;
     } while (c != rootWithMinKey.child);
     rootWithMinKey.child = null; // removed all children
     rootWithMinKey.insert(c);
   }
   if (debugRemoveMin) {
     System.out.println("  roots after inserting children: " + toString());
   }


   /// Phase 2-a: handle the case where we delete the last myKey:
   if (rootWithMinKey.next == rootWithMinKey) {
     if (debugRemoveMin) System.out.println("  removed the last");
     assert(count == 0);
     rootWithMinKey = null;
     return;
   }

   /// Phase 2: merge roots with the same degree:
   // make room for a new degree
   //degreeRoots.setSize(maxDegree + 1);
   HeapNode<Data> currentPointer = rootWithMinKey.next;
   int maxDegree = 0;
   do {
     if (currentPointer.degree > maxDegree)
       maxDegree = currentPointer.degree;
     currentPointer = currentPointer.next;
   } while (currentPointer != rootWithMinKey);
   Vector<HeapNode<Data>> degreeRoots = new Vector<HeapNode<Data>>(maxDegree + 2);
   for (int i = 0; i < maxDegree + 2; ++i) degreeRoots.add(null);
   currentPointer = rootWithMinKey.next;
   int currentDegree;
   do {
     currentDegree = currentPointer.degree;
     if (debugRemoveMin) {
       System.out.println("  roots starting from currentPointer: " +
                          currentPointer.printAll());
       System.out.println("  checking root " + currentPointer
                          + " with degree " + currentDegree);
     }

     HeapNode<Data> current = currentPointer;
     currentPointer = currentPointer.next;
      // merge the two roots with the same degree:
     while (degreeRoots.get(currentDegree) != null) {
       // another root with the same degree
       HeapNode<Data> other = degreeRoots.get(currentDegree);
       if (_comparator.compare(current.data, other.data) > 0) {
         HeapNode<Data> help = current;
         current = other;
         other = help;
       }
       // now current.key() <= other.key() - make other a child of current:
       other.remove(); // remove from list of roots
       current.addChild(other);
       if (debugRemoveMin)
         System.out.println("  added " + other + " as child of " + current);
       degreeRoots.set(currentDegree, null); //
       ++currentDegree;
       while (currentDegree >= degreeRoots.size())
         degreeRoots.add(null);
     }
     // keep the current root as the first of its degree in the degrees array:
     degreeRoots.set(currentDegree, current);
   } while (currentPointer != rootWithMinKey);

   /// Phase 3: remove the current root, and calculate the new rootWithMinKey:
   //delete rootWithMinKey;
   rootWithMinKey.degree = -1; // mark it as removed
   rootWithMinKey = null;

   for (int d = 0; d < degreeRoots.size(); ++d) {
     if (debugRemoveMin) System.out.print("  degree " + d + ": ");
     HeapNode<Data> current = degreeRoots.get(d);
     if (current != null) {
       if (debugRemoveMin) System.out.println(" " + current);

       current.next = current.previous = current;
       insertNode(current);
     } else {
       if (debugRemoveMin) System.out.println("  no node");
     }
   }
 }
/** remove the minimum element from this heap.
  *
  *  @prerequisite the heap may not be empty, otherwise, an EmptyHeapException
  */
remove the minimum element from this heap.
@prerequisite the heap may not be empty, otherwise, an EmptyHeapException
remove the minimum element from this heap . @prerequisite the heap may not be empty otherwise an EmptyHeapException
public void removeMinimum() {  
   if (rootWithMinKey == null)
     throw new EmptyHeapException("trying to remove from an empty heap");
   if (debug) System.out.println("removeMinimum");
   --count;
   if (rootWithMinKey.child != null) {
     if (debugRemoveMin) {
       System.out.println("root's children: " +
                          rootWithMinKey.child.printAll());
     }
     HeapNode<Data> c = rootWithMinKey.child;
     do {
       c.parent = null;
       c = c.next;
     } while (c != rootWithMinKey.child);
     rootWithMinKey.child = null; 
     rootWithMinKey.insert(c);
   }
   if (debugRemoveMin) {
     System.out.println("  roots after inserting children: " + toString());
   }
   if (rootWithMinKey.next == rootWithMinKey) {
     if (debugRemoveMin) System.out.println("  removed the last");
     assert(count == 0);
     rootWithMinKey = null;
     return;
   }
   HeapNode<Data> currentPointer = rootWithMinKey.next;
   int maxDegree = 0;
   do {
     if (currentPointer.degree > maxDegree)
       maxDegree = currentPointer.degree;
     currentPointer = currentPointer.next;
   } while (currentPointer != rootWithMinKey);
   Vector<HeapNode<Data>> degreeRoots = new Vector<HeapNode<Data>>(maxDegree + 2);
   for (int i = 0; i < maxDegree + 2; ++i) degreeRoots.add(null);
   currentPointer = rootWithMinKey.next;
   int currentDegree;
   do {
     currentDegree = currentPointer.degree;
     if (debugRemoveMin) {
       System.out.println("  roots starting from currentPointer: " +
                          currentPointer.printAll());
       System.out.println("  checking root " + currentPointer
                          + " with degree " + currentDegree);
     }
     HeapNode<Data> current = currentPointer;
     currentPointer = currentPointer.next;
     while (degreeRoots.get(currentDegree) != null) {
       HeapNode<Data> other = degreeRoots.get(currentDegree);
       if (_comparator.compare(current.data, other.data) > 0) {
         HeapNode<Data> help = current;
         current = other;
         other = help;
       }
       other.remove(); 
       current.addChild(other);
       if (debugRemoveMin)
         System.out.println("  added " + other + " as child of " + current);
       degreeRoots.set(currentDegree, null); 
       ++currentDegree;
       while (currentDegree >= degreeRoots.size())
         degreeRoots.add(null);
     }
      keep the current root as the first of its degree in the degrees array:
     degreeRoots.set(currentDegree, current);
   } while (currentPointer != rootWithMinKey);
   / Phase 3: remove the current root, and calculate the new rootWithMinKey:
   delete rootWithMinKey;
   rootWithMinKey.degree = -1;  mark it as removed
   rootWithMinKey = null;
   for (int d = 0; d < degreeRoots.size(); ++d) {
     if (debugRemoveMin) System.out.print("  degree " + d + ": ");
     HeapNode<Data> current = degreeRoots.get(d);
     if (current != null) {
       if (debugRemoveMin) System.out.println(" " + current);
       current.next = current.previous = current;
       insertNode(current);
     } else {
       if (debugRemoveMin) System.out.println("  no node");
     }
   }
 }
public void removeMinimum ( ) { if ( rootWithMinKey == null ) throw new EmptyHeapException ( "trying to remove from an empty heap" ) ; if ( debug ) System . out . println ( "removeMinimum" ) ; -- count ; if ( rootWithMinKey . child != null ) { if ( debugRemoveMin ) { System . out . println ( "root's children: " + rootWithMinKey . child . printAll ( ) ) ; } HeapNode < Data > c = rootWithMinKey . child ; do { c . parent = null ; c = c . next ; } while ( c != rootWithMinKey . child ) ; rootWithMinKey . child = null ; rootWithMinKey . insert ( c ) ; } if ( debugRemoveMin ) { System . out . println ( "  roots after inserting children: " + toString ( ) ) ; } if ( rootWithMinKey . next == rootWithMinKey ) { if ( debugRemoveMin ) System . out . println ( "  removed the last" ) ; assert ( count == 0 ) ; rootWithMinKey = null ; return ; } HeapNode < Data > currentPointer = rootWithMinKey . next ; int maxDegree = 0 ; do { if ( currentPointer . degree > maxDegree ) maxDegree = currentPointer . degree ; currentPointer = currentPointer . next ; } while ( currentPointer != rootWithMinKey ) ; Vector < HeapNode < Data > > degreeRoots = new Vector < HeapNode < Data > > ( maxDegree + 2 ) ; for ( int i = 0 ; i < maxDegree + 2 ; ++ i ) degreeRoots . add ( null ) ; currentPointer = rootWithMinKey . next ; int currentDegree ; do { currentDegree = currentPointer . degree ; if ( debugRemoveMin ) { System . out . println ( "  roots starting from currentPointer: " + currentPointer . printAll ( ) ) ; System . out . println ( "  checking root " + currentPointer + " with degree " + currentDegree ) ; } HeapNode < Data > current = currentPointer ; currentPointer = currentPointer . next ; while ( degreeRoots . get ( currentDegree ) != null ) { HeapNode < Data > other = degreeRoots . get ( currentDegree ) ; if ( _comparator . compare ( current . data , other . data ) > 0 ) { HeapNode < Data > help = current ; current = other ; other = help ; } other . remove ( ) ; current . addChild ( other ) ; if ( debugRemoveMin ) System . out . println ( "  added " + other + " as child of " + current ) ; degreeRoots . set ( currentDegree , null ) ; ++ currentDegree ; while ( currentDegree >= degreeRoots . size ( ) ) degreeRoots . add ( null ) ; } degreeRoots . set ( currentDegree , current ) ; } while ( currentPointer != rootWithMinKey ) ; rootWithMinKey . degree = - 1 ; rootWithMinKey = null ; for ( int d = 0 ; d < degreeRoots . size ( ) ; ++ d ) { if ( debugRemoveMin ) System . out . print ( "  degree " + d + ": " ) ; HeapNode < Data > current = degreeRoots . get ( d ) ; if ( current != null ) { if ( debugRemoveMin ) System . out . println ( " " + current ) ; current . next = current . previous = current ; insertNode ( current ) ; } else { if ( debugRemoveMin ) System . out . println ( "  no node" ) ; } } }
remove the minimum element from this heap.
remove the minimum element from this heap .
// Fibonacci-Heap-Extract-Min, CONSOLIDATE /// Phase 1: Make all the removed root's children new roots: // Make all children of root new roots: // removed all children /// Phase 2-a: handle the case where we delete the last myKey: /// Phase 2: merge roots with the same degree: // make room for a new degree //degreeRoots.setSize(maxDegree + 1); // merge the two roots with the same degree: // another root with the same degree // now current.key() <= other.key() - make other a child of current: // remove from list of roots // // keep the current root as the first of its degree in the degrees array: /// Phase 3: remove the current root, and calculate the new rootWithMinKey: //delete rootWithMinKey; // mark it as removed