优先级队列
一、PriorityQueue
PriorityQueue是优先级队列，它实现了Queue接口，它的队列长度
没有限制，与一般队列的区别是，它有优先级概念，每个元素都有优先
级，队头的元素永远都是优先级最高的。PriorityQueue内部是用堆实现的。
一、基本用法
主要构造方法:
public PriorityQueue()
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
public PriorityQueue(Collection<? extends E> c) //动态数组大小等于容器中元素的个数
PriorityQueue使用动态数组initialCapacity表示初始数组的大小。举例：
PriorityQueue<Integer> ints = new PriorityQueue<>();
ints.offer(10);
ints.add(28);
ints.addAll(Arrays.asList(22, 33, 55, 66));
while (ints.peek() != null) {
System.out.println(ints.poll() + " ");
}
二、实现原理
内部成员：
private transient Object[] queue;
private int size = 0;
private final Comparator<? super E> comparator;
private transient int modCount = 0;
构造方法：
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
if(initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
添加元素的代码
public boolean offer(E e) {
if(e == null)
throw new NullPointerException();
modCount++;
int i = size;
if(i >= queue.length) //先确保数组长度是否足够，如果不够，用grow方法扩展
grow(i + 1);
size = i + 1;
if(i == 0) //如果是第一次添加
queue[0] = e;
else //否则将其放入最后一个位置，并向上调整
siftUp(i, e);return true;
}
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64)
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if(newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
private void siftUp(int k, E x) {
if(comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
private void siftUpUsingComparator(int k, E x) {
while(k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if(comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
查看元素头部元素：
public E peek() {
if(size == 0)
return null;
return (E) queue[0];
}
删除头部元素：略
三、总结
1）实现了优先级队列，最先出队的总是优先级最高的，即排序中的第一个。
2）优先级可以有相同的，内部元素不是完全有序的，如果遍历输出，除了第一个其他没有特定顺序。、
3）查看头部元素，入队出队的效率都很高
4）根据值查找和删除元素的效率很低。