// FibHeap.java

public class FibHeap
{
   private Node min;
   private int n;

   public FibHeap(){}

   private void cascadingCut(Node y)
   {
      Node z = y.parent;
      if (z != null)
         if (!y.mark)
            y.mark = true;
         else
         {
            cut(y, z);
            cascadingCut(z);
         }
   }

   private void consolidate()
   {
      int D = n + 1;
      Node A[] = new Node[D];
      for(int i = 0; i < D; i++)
         A[i] = null;

      int k = 0;
      Node x = min;
      if (x != null)
      {
         k++;
         for(x = x.right; x != min; x = x.right)
            k++;
      }
      while (k > 0)
      {
         int d = x.degree;
         Node rightNode = x.right;
         while (A[d] != null)
         {
            Node y = A[d];
            if (x.cost > y.cost)
            {
               Node temp = y;
               y = x;
               x = temp;
            }
            link(y, x);
            A[d] = null;
            d++;
         }

         A[d] = x;
         x = rightNode;
         k--;
     }

     min = null;
     for(int i = 0; i < D; i++)
        if (A[i] != null)
           if (min != null)
           {
              A[i].left.right = A[i].right;
              A[i].right.left = A[i].left;
              A[i].left = min;
              A[i].right = min.right;
              min.right = A[i];
              A[i].right.left = A[i];
              if (A[i].cost < min.cost)
                 min = A[i];
           }
           else
              min = A[i];
   }

   private void cut(Node x, Node y)
   {
      x.left.right = x.right;
      x.right.left = x.left;
      y.degree--;
      if (y.child == x)
         y.child = x.right;
      if (y.degree == 0)
         y.child = null;
      x.left = min;
      x.right = min.right;
      min.right = x;
      x.right.left = x;
      x.parent = null;
      x.mark = false;
   }

   public void decreaseKey(Node x, int c)
   {
      if (c > x.cost)
      {
         System.err.println("Error: new key is greater than current key.");
         return;
      }
      x.cost = c;
      Node y = x.parent;
      if ((y != null) && (x.cost < y.cost))
      {
         cut(x, y);
         cascadingCut(y);
      }
      if (x.cost < min.cost)
         min = x;
   }

   public void delete(Node node)
   {
      decreaseKey(node, Integer.MIN_VALUE);
      removeMin();
   }

   public boolean empty()
   {
      return min == null;
   }

   public Node insert(Node toInsert)
   {
      if (min != null)
      {
         toInsert.left = min;
         toInsert.right = min.right;
         min.right = toInsert;
         toInsert.right.left = toInsert;
         if (toInsert.cost < min.cost)
            min = toInsert;
      }
      else
         min = toInsert;
      n++;
      return toInsert;
   }

   private void link(Node node1, Node node2)
   {
      node1.left.right = node1.right;
      node1.right.left = node1.left;
      node1.parent = node2;
      if (node2.child == null)
      {
         node2.child = node1;
         node1.right = node1;
         node1.left = node1;
      }
      else
      {
         node1.left = node2.child;
         node1.right = node2.child.right;
         node2.child.right = node1;
         node1.right.left = node1;
      }
      node2.degree++;
      node1.mark = false;
   }

   public Node min()
   {
      return min;
   }

   public Node removeMin()
   {
      Node z = min;
      if (z != null)
      {
         int i = z.degree;
         Node x = z.child;
         while (i > 0)
         {
            Node nextChild = x.right;
            x.left.right = x.right;
            x.right.left = x.left;
            x.left = min;
            x.right = min.right;
            min.right = x;
            x.right.left = x;
            x.parent = null;
            x = nextChild;
            i--;
         }
         z.left.right = z.right;
         z.right.left = z.left;
         if(z == z.right)
            min = null;
         else
         {
            min = z.right;
            consolidate();
         }
         n--;
      }
      return z;
   }

   public int size()
   {
      return n;
   }

   public static FibHeap union(FibHeap heap1, FibHeap heap2)
   {
      FibHeap heap = new FibHeap();
      if ((heap1 != null) && (heap2 != null))
      {
         heap.min = heap1.min;
         if (heap.min != null)
         {
            if (heap2.min != null)
            {
               heap.min.right.left = heap2.min.left;
               heap2.min.left.right = heap.min.right;
               heap.min.right = heap2.min;
               heap2.min.left = heap.min;
               if (heap2.min.cost < heap1.min.cost)
                  heap.min = heap2.min;
            }
         }
         else
            heap.min = heap2.min;
         heap.n = heap1.n + heap2.n;
      }
      return heap;
   }

}