/* Java implementation of maxiphobic heaps as described in
**   Alternatives to Two Classic Data Structures
**   Chris Okasaki
**   SIGCSE 2005
**
** Implements mergeable priority queues of integers.
** Can easily be adapted to other key types.
*/

public class Maxiphobic {

   public Maxiphobic() {
      root = null;
   }

   public int findMin() throws EmptyException {
      if (root == null) {
         throw new EmptyException();
      }
      else {
         return root.value;
      }
   }

   public int deleteMin() throws EmptyException {
      if (root == null) {
         throw new EmptyException();
      }
      else {
         int min = root.value;
         root = merge(root.left, root.right);
         return min;
      }
   }

   public void insert(int value) {
      Heap newHeap = new Heap();
      newHeap.value = value;
      newHeap.size = 1;
      newHeap.left = null;
      newHeap.right = null;
      
      root = merge(root, newHeap);
   }

   public void merge(Maxiphobic other) {
      if (other == null || other == this) return;

      root = merge(root, other.root);
      other.root = null;
   }

   public int size() {
      if (root == null) {
         return 0;
      }
      else {
         return root.size;
      }
   }

   public static class EmptyException extends Exception {}

   /***** Implementation details *****/

   private static class Heap {
      private int value;
      private int size;
      private Heap left;
      private Heap right;
   }

   private Heap root;
   
   private static Heap merge(Heap heap1, Heap heap2) {
      if (heap1 == null) return heap2;
      if (heap2 == null) return heap1;

      // force heap1 to have smaller root
      if (heap2.value < heap1.value) {
         // swap heap1 and heap2
         Heap tmp = heap1;
         heap1 = heap2;
         heap2 = tmp;
      }

      // calculate size of merged tree
      heap1.size += heap2.size;

      // get the three subtrees
      Heap A = heap1.left;
      Heap B = heap1.right;
      Heap C = heap2;

      // force A to be biggest of the three subtrees
      if (size(B) > size(A)) {
         // swap A and B
         Heap tmp = A;
         A = B;
         B = tmp;
      }
      if (size(C) > size(A)) {
         // swap A and C
         Heap tmp = A;
         A = C;
         C = tmp;
      }

      // rebuild tree
      heap1.left = A;
      heap1.right = merge(B, C);
      return heap1;
   }

   private static int size(Heap heap) {
      if (heap == null) {
         return 0;
      }
      else {
         return heap.size;
      }
   }
}