package Demo;
import java.util.NoSuchElementException;
/*
 * 小頂堆 java使用堆結構實現優先隊列
 */
public class JPriorityQueue<E> {
  @SuppressWarnings("hiding")
    class QueueNode<E> {
    int capacity;
    int size;
    E[] queue;
    QueueNode(int capacity) {
      this.capacity = capacity;
    }
  }
  QueueNode<E> node;
  public void print()
  {
    E[] objs=this.node.queue;
    for(int i=0;i<this.node.size;i++)
    {
      System.out.print(objs[i]+" ");
    }
    System.out.println();
  }
  @SuppressWarnings("unchecked")
    public JPriorityQueue(int capacity) {
    node = new QueueNode<E>(capacity);
    node.size = 0;
    node.queue = (E[]) new Object[capacity + 1];
  }
  public void add(E x) {
    int k = node.size;
    while (k > 0) {
      int parent = (k - 1) / 2;
      E data = node.queue[parent];
      @SuppressWarnings({ "unchecked", "rawtypes" })
      Comparable<E> key = (Comparable) x;
      if (key.compareTo(data) >= 0)
        break;
      node.queue[k] = data;
      k = parent;
    }
    node.queue[k] = x;
    node.size++;
  }
  public E remove() {
    int parent = 0;
    if (node.size == 0) {
      throw new NoSuchElementException("queue is null");
    }
    E min = node.queue[0];// top
    E last = node.queue[node.size - 1];// last
    node.queue[0] = last;// add the last to top
    node.queue[node.size - 1] = null;
    node.size--;
    @SuppressWarnings("unchecked")
    Comparable<? super E> complast = (Comparable<? super E>) last;
    if (node.size == 2 && complast.compareTo(node.queue[1]) > 0) { // 只剩下最后兩個結點，進行比較
      node.queue[0] = node.queue[1];
      node.queue[1] = last;
    }
    if (node.size > 2) { // 大于三個結點的，向下旋轉
      while (parent < node.size / 2) {
        int left = 2 * parent + 1;// left child
        int right = left + 1;// right child
        E root = node.queue[parent];
        @SuppressWarnings("unchecked")
        Comparable<? super E> comproot = (Comparable<? super E>) root;
        if (comproot.compareTo(node.queue[left]) < 0
          && comproot.compareTo(node.queue[right]) < 0)
          break;
        @SuppressWarnings("unchecked")
        Comparable<? super E> compleft = (Comparable<? super E>) node.queue[left];
        if (compleft.compareTo(node.queue[right]) <= 0) {
          node.queue[parent] = node.queue[left];
          node.queue[left] = root;
          parent = left;
        } else {
          node.queue[parent] = node.queue[right];
          node.queue[right] = root;
          parent = right;
        }
        if (right * 2 >= node.size)
          break;
      }
    }
    return min;
  }
  public static void main(String[] args) {
    System.out.println("億速云測試結果：");
    JPriorityQueue<String> queue = new JPriorityQueue<String>(10);
    queue.add("Z");
    queue.add("B");
    queue.add("QZA");
    queue.add("QBA");
    queue.add("EAA");
    queue.add("A");
    queue.print();
    // queue.remove();
    // queue.remove();
    // queue.remove();
    // queue.remove();
    // queue.remove();
    System.out.println(queue.remove());
    System.out.println(queue.remove());
    System.out.println(queue.remove());
    System.out.println(queue.remove());
    System.out.println(queue.remove());
    System.out.println(queue.remove());
  }
}