day1-优先队列

（#每日一点点）day1-优先队列

优先队列（PriorityQueue）

优先队列是queue接口的一个实现类，底层为平衡二叉堆。PriorityQueue初始容量为11(自动增加)，不能存储null元素以及其他不能进行比较的对象。PriorityQueue实现了Collection和iterator接口，但是不能保证使用iterator中的迭代器以任何特定顺序遍历优先级队列的元素，如有需要，使用Arrays.sort(pq.toArray())方式遍历。该实现类是非同步的，线程不安全。如有需要，使用线程同步的PriorityBlockingQueue类。该类为排队和出列方法 offer()、poll()、 remove()和 add()提供了O(log(n))时间；remove(Object)和contains(Object)方法提供了线性时间；peek()、element()和size()检索方法提供了常量时间。

创建优先队列

默认情况下PriorityQueue按照升序的顺序排列（逆序可以自定义比较类）。队列保存的是基本数据类型的包装类。

PriorityQueue<Integer> pq= new PriorityQueue<Integer>();

对于自定义类来说，需要自定义比较类。例如：

PriorityQueue<List<Integer>> array = new PriorityQueue<List<Integer>>(new Comparator<List<Integer>>(){
            public int compare(List<Integer> v1 , List<Integer> v2){
                return v1.get(2) - v2.get(2);
            }
        });

扩容

如果规模较小，则扩大一倍；否则扩大50%。

int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));

常用方法

peek()//返回队首元素（队首元素不出队列）
poll()//返回队首元素，队首元素出队列
add()//添加元素
offer()//添加元素
size()//返回队列元素个数
contains(Object o)//是否包含特定元素
clear()//清除所有元素
removeAt(int i)//移除第i个元素
isEmpty()//判断队列是否为空，为空返回true,不空返回false