/**
 * @auther zhangxufeng@uworks.cc 2016/06/03
 */
public class BinaryHeap<AnyType extends Comparable<? super AnyType>> {
  public BinaryHeap() {
    enlargeArray(DEFAULT_CAPACITY);
  }

  public BinaryHeap(int capacity) {
    int tmp = capacity;
    if (capacity < DEFAULT_CAPACITY) {
      tmp = DEFAULT_CAPACITY;
    }

    enlargeArray(tmp);
  }

  public BinaryHeap(AnyType[] items) {
    currentSize = items.length;
    enlargeArray(enlargeTimes());

    int i = 0;
    for (AnyType item : items) {
      array[++i] = item;
    }
    buildHeap();
  }

  public void insert(AnyType x) {
    if (currentSize == array.length - 1) {
      enlargeArray(array.length * 2 + 1);
    }

    int hole = ++currentSize;
    while (hole > 1 && x.compareTo(array[hole / 2]) < 0) {
      array[hole] = array[hole / 2];
      hole /= 2;
    }
    array[hole] = x;
  }

  public void insertFromTop(AnyType x) {
    if (currentSize == array.length - 1) {
      enlargeArray(array.length * 2 + 1);
    }

    AnyType item = x;

    // 获取要交换的路径
    int index = (currentSize + 1) / 2;
    int[] path = new int[height(1) + 1];
    for (int i = 0; i < path.length; i++) {
      path[i] = index;
      index /= 2;
    }

    for (int i = path.length - 1; i >= 0; i--) {
      if (path[i] <= 0) {
        continue;
      }
      item = compare(item, path[i]);
    }
    array[++currentSize] = item;
  }

  private AnyType compare(AnyType item, int index) {
    if (item.compareTo(array[index]) < 0) {
      AnyType tmp = item;
      item = array[index];
      array[index] = tmp;
    }
    return item;
  }

  private int height(int index) {
    int tmp = 1, i = 0;
    while (tmp * 2 <= index) {
      tmp *= 2;
    }

    while (tmp * 2 <= currentSize) {
      tmp *= 2;
      i++;
    }

    return i;
  }

  public AnyType findMin() {
    return null;
  }

  public int size() {
    return currentSize;
  }

  private int[] path(int root) {
    int[] result = new int[height(root) + 1];
    for (int i = currentSize, j = result.length - 1; i >= 1; i /= 2) {
      result[j--] = i;
    }
    return result;
  }

  public AnyType deleteMin() throws UnderflowException {
    if (isEmpty()) {
      throw new UnderflowException();
    }

    AnyType minItem = findMin();
    array[1] = array[currentSize--];
    percolateDown(1);

    return minItem;
  }

  public boolean isEmpty() {
    return currentSize == 0;
  }

  public void makeEmpty() {
    for (int i = 0; i < array.length; i++) {
      array[i] = null;
    }
  }

  private static final int DEFAULT_CAPACITY = 10;

  private int currentSize;
  private AnyType[] array;

  private void percolateDown(int hole) {
    int child;
    AnyType tmp = array[hole];

    while ((child = hole * 2) <= currentSize) {
      if (child < currentSize && array[child + 1].compareTo(array[child]) < 0) {
        child++;
      }
      System.out.println("hole:" + hole + " child:" + child);

      if (array[child].compareTo(tmp) < 0) {
        array[hole] = array[child];
      } else {
        break;
      }
      hole = child;
    }
    array[hole] = tmp;
  }

  private void buildHeap() {
    for (int i = currentSize / 2; i > 0; i--) {
      percolateDown(i);
    }
  }

  private void enlargeArray(int newSize) {
    if (newSize <= currentSize) {
      newSize = enlargeTimes();
    }

    AnyType[] old = array;
    array = ((AnyType[]) new Comparable[newSize]);
    if (null != old) {
      for (int i = 0; i < old.length; i++) {
        array[i] = old[i];
      }
    }
  }

  private int enlargeTimes() {
    return (currentSize + 2) * 11 / 10;
  }

  public void print() {
    for (int i = 1; i <= currentSize; i++) {
      System.out.print(array[i] + "\t");
    }
  }
}

class UnderflowException extends Exception {}

/**
 * Created by Administrator on 2016/6/2.
 */
public class BinomialQueue<AnyType extends Comparable<? super AnyType>> {
  public BinomialQueue() {

  }

  public BinomialQueue(AnyType item) {

  }

  public void merge(BinomialQueue<AnyType> rhs) {
    if (this == rhs) {
      return;
    }

    currentSize += rhs.currentSize;

    if (currentSize > capacity()) {
      int maxLength = Math.max(theTrees.length, rhs.theTrees.length);
      expandTheTrees(maxLength + 1);
    }

    Node<AnyType> carry = null;
    for (int i = 0, j = 1; j < currentSize; i++, j*= 2) {
      Node<AnyType> t1 = theTrees[i];
      Node<AnyType> t2 = i < rhs.theTrees.length ? rhs.theTrees[i] : null;

      int whichCase = t1 == null ? 0 : 1;
      whichCase += t2 == null ? 0 : 1;
      whichCase += carry == null ? 0 : 4;

      switch (whichCase) {
        case 0:
        case 1:
          break;
        case 2:
          theTrees[i] = t2;
          rhs.theTrees[i] = null;
          break;
        case 4:
          theTrees[i] = carry;
          carry = null;
          break;
        case 3:
          carry = combineTrees(t1, t2);
          theTrees[i] = rhs.theTrees[i] = null;
          break;
        case 5:
          carry = combineTrees(t1, carry);
          theTrees[i] = null;
          break;
        case 6:
          carry = combineTrees(t2, carry);
          rhs.theTrees[i] = null;
          break;
        case 7:
          theTrees[i] = carry;
          carry = combineTrees(t1, t2);
          rhs.theTrees[i] = null;
          break;
        default:
      }
    }

    for (int k = 0; k < rhs.theTrees.length; k++) {
      rhs.theTrees[k] = null;
    }
    rhs.currentSize = 0;
  }

  public void insert(AnyType x) {
    merge(new BinomialQueue<>(x));
  }

  public AnyType findMin() {

  }

  public AnyType deleteMin() throws UnderflowException {
    if (isEmpty()) {
      throw new UnderflowException();
    }

    int minIndex = findMinIndex();
    AnyType minItem = theTrees[minIndex].element;

    Node<AnyType> deletedTree = theTrees[minIndex].leftChild;

    BinomialQueue<AnyType> deletedQueue = new BinomialQueue<>();
    deletedQueue.expandTheTrees(minIndex + 1);

    deletedQueue.currentSize = (1 << minIndex) - 1;
    for (int j = minIndex - 1; j >= 0; j--) {
      deletedQueue.theTrees[j] = deletedTree;
      deletedTree = deletedTree.nextSibling;
      deletedQueue.theTrees[j].nextSibling = null;
    }

    theTrees[minIndex] = null;
    currentSize -= deletedQueue.currentSize + 1;
    merge(deletedQueue);

    return minItem;
  }

  public boolean isEmpty() {
    return currentSize == 0;
  }

  public void makeEmpty(){

  }

  private static class Node<AnyType> {
    Node(AnyType theElement) {
      this(theElement, null, null);
    }

    Node(AnyType theElement, Node<AnyType> lt, Node<AnyType> nt) {
      element = theElement;
      leftChild = lt;
      nextSibling = nt;
    }

    AnyType element;
    Node<AnyType> leftChild;
    Node<AnyType> nextSibling;
  }

  private static final int DEFAULT_TREES = 1;

  private int currentSize;
  private Node<AnyType>[] theTrees;

  private void expandTheTrees(int newNumTrees) {

  }

  private Node<AnyType> combineTrees(Node<AnyType> t1, Node<AnyType> t2) {
    if (t1.element.compareTo(t2.element) > 0) {
      return combineTrees(t2, t1);
    }
    t2.nextSibling = t1.leftChild;
    t1.leftChild = t2;
    return t1;
  }

  private int capacity() {
    return (1 << theTrees.length) - 1;
  }

  private int findMinIndex() {

  }
}

class UnderflowException extends Exception {}

/**
 * Created by Administrator on 2016/6/1.
 */
public class LeftistHeap<AnyType extends Comparable<? super AnyType>> {
  public LeftistHeap() {
    root = null;
  }

  public void merge(LeftistHeap<AnyType> rhs) {
    if (this == rhs) {
      return;
    }

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

  public void insert(AnyType x) {
    root = merge(new Node<>(x), root);
  }

  public AnyType findMin() {
    return root.element;
  }

  public AnyType deleteMin() {
    AnyType element = root.element;
    root = merge(root.left, root.right);
    return element;
  }

  public boolean isEmpty() {
    return null == root;
  }

  public void makeEmpty() {
    root = null;
  }

  private static class Node<AnyType> {
    Node(AnyType theElement) {
      this(theElement, null, null);
    }

    Node(AnyType theElement, Node<AnyType> lt, Node<AnyType> rt) {
      element = theElement;
      left = lt;
      right = rt;
      npl = 0;
    }

    AnyType element;
    Node<AnyType> left;
    Node<AnyType> right;
    int npl;
  }

  private Node<AnyType> root;

  private Node<AnyType> merge(Node<AnyType> h1, Node<AnyType> h2) {
    if (null == h1) {
      return h2;
    }
    if (null == h2) {
      return h1;
    }
    if (h1.element.compareTo(h2.element) < 0) {
      return merge1(h1, h2);
    } else {
      return merge1(h2, h1);
    } 
  }

  private Node<AnyType> merge1(Node<AnyType> h1, Node<AnyType> h2) {
    if (h1.left == null) {
      h1.left = h2;
    } else {
      h1.right = merge(h1.right, h2);
      if (h1.left.npl < h1.right.npl) {
        swapChildren(h1);
      }
      h1.npl = h1.right.npl + 1;
    }

    return h1;
  }

  private void swapChildren(Node<AnyType> t) {
    
  }
}