public interface Queue<E> {

    //队列是否为空
    boolean isEmpty();

    //队列的大小
    int size();

    //入队
    void enQueue(E element);

    //出队
    E deQueue();
}

/**
 * 基于有序数组的实现的优先队列
 * @author Alent
 * @param <E>
 */
public class PriorityQueue<E extends Comparable<E>> implements Queue<E>{
    private E[] elements;
    private int size=0;
    
    @SuppressWarnings("unchecked")
    public PriorityQueue() {
        elements = (E[])new Comparable[1]; 
    }
    
    @Override public int size() {return size;}

    @Override public boolean isEmpty() {return size == 0;}

    @Override
    public void enQueue(E element) {
        if(size == elements.length) {
            resizingArray(2*size);//若数组已满将长度加倍
        }
        elements[size++] = element;
        insertSort(elements);
    }

    @Override
    public E deQueue() {
        E element = elements[--size];
        elements[size] = null;     //注意：避免对象游离
        if(size > 0 && size == elements.length/4) {
            resizingArray(elements.length/2);//小于数组1/4,将数组减半
        }
        return element;
    }
    
    //插入排序，由于前面n-1个元素是有序的，这里只插入最后一个元素
    public void insertSort(E[] a) {
        int N = size -1; //最后一个元素是size-1，不是a.length-1
        if(N == 0) return;
        int num = binaryFind(a, a[N], 0, N-1);
        E temp = a[N];
        //num后的元素向后移动
        for (int j = N; j > num; j--) {
           a[j] = a[j-1];
        }
        a[num] = temp;
    }

    //找出元素应在数组中插入的位置
    public int binaryFind(E[] a, E temp, int down, int up) {
        if(up<down || up>a.length || down<0) {
            System.out.println("下标错误");
        }
        if(temp.compareTo(a[down]) < 0) return down;
        if(temp.compareTo(a[up]) > 0) return up+1;
        int mid = (up-down)/2 + down;
        if(temp.compareTo(a[mid]) == 0) {
            return mid + 1;
        }else