Java的容器分成四个系列：Set, List, Queue,Map，除Map外，其余三个都实现了Collection接口，List和Queue实现顺序存储，Map实现了K-V对。
本章分析其中实现较为简单的Queue系列
一、类实现/继承体系结构
为了对整个Queue实现/继承体系有个全貌，先将体系结构图画出来：
二、关键数据成员
（1）存储结构
PriorityQueue内部使用平衡二叉树（小根堆）保存元素，底层采用的数据结构是数组：
transientObject[] queue;
利用数组保存二叉树，那么某个节点queue[n]的左子树和右子树分别是queue[2*n+1] 和queue[2*(n+1)]。
队列queue的默认初始化大小(DEFAULT_INITIAL_CAPACITY)是11。
（2）比较运算符
优先级队列要么根据比较运算符进行排序，当运算符为null时，则根据元素的自然顺序进行排序，最小值是queue[0]。
在PriorityQueue中，有一个成员变量用于记录采取的比较运算符：
private final Comparator<? super E> comparator;
PriorityQueue要求外部传入的Comparator比较器的类型必须是当前正在构造类的本身或者是其父类、祖父类。。。总之，在继承层次上，大于等于它自身
为什么这么要求呢？
我琢磨着原因应该是这样：
一个类的比较，最终要落到对其数据成员的操作，得到比较结果，子类是继承了父类的数据成员（也许是部分，除掉一些在父类中的private成员，后面再讨论），也就是说，利用父类的Comparator进行比较时，对子类也是适用的，但反过来，子类可能定义了一些新的数据成员，是父类中没有的，如果子类的Comparator在compare函数中使用这些新的数据成员比较，那么对父类是不适用的，所以，子类可以使用父类的Comparator，反过来不行。
对于父类使用私有数据成员实现compare函数，分两种情况：
一种子类可以通过构造函数，对父类的私有成员赋值，如果构造函数中有对私有成员初始化的参数，那么这种情况也会子类的比较起作用；
另一种情况，子类本身无法使用父类的私有数据成员，又没有办法改变它，那么父类的comparator对子类的排序不起作用。
（3）修改次数
transientint modCount = 0;
数据成员modCount用于记录queue队列被修改的次数
（4）
三、构造函数
PriorityQueue提供了多种形式的构造函数，在此不一一列举，就参数来说，主要包括，队列(queue)初始化大小（initialCapacity）值、比较运算符、其他集合（包括PriorityQueue或者别的类型的集合，比如Set）
这里要讲下以下几个构造函数：
public MyPriorityQueue(Collection<?extends E> c)
<? extends E>表示c中的元素(?)只能是类型E的子类，这样其实将一个子类对象赋值给了一个父类对象，父类对象指向了一个子类对象，即多态，比如：
class Fruit {
}
class Apple extends Fruit {
}
List<Apple>appleL= newArrayList<Apple>();
appleL.add(new Apple("red"));
appleL.add(new Apple("green"));
Queue<Fruit>fruitQ= newPriorityQueue<Fruit>(appleL);
反过来就会出错了，如果用一个存放Fruit的List作为PriorityQueue的构造函数的参数就会出错了。
注意，上面是简化的写法，代码是无法编译通过的，因为PriorityQueue在存入对象时涉及到对象之间的比较，那就要去存入的对象之间可以进行比较，一种是传递了Comparator，实现对象的比较；另一种是类实现Comparable接口的比较函数compareTo，有些类本身支持比较，比如String，Integer，但对于自定义的类，那就要求实现者自己实现compareTo，当调用PriorityQueue构造函数时没有传递Comparator，PriorityQueue在比较元素的时候就调用类的compareTo进行比较，如果二者都没有提供，那就会抛异常了。下面是实现了compareTo的例子，如：
class Fruit implements Comparable<Fruit> {
protected String name;
public Fruit(String name) {
this.name = name;
}
public String getName() {
returnname;
}
@Override
publicint compareTo(Fruit o) {
returnthis.name.compareTo(o.getName());
}
}
class Apple extends Fruit {
public Apple(String name) {
super(name);
}
}
四、堆操作
PriorityQueue底层使用堆进行存储，后面要讲的队列的增删改查很多时候涉及到对堆的操作。堆的操作主要包括两个：
siftUp
siftDown
PriorityQueue实现了标准的heap上浮（sift up）和下沉（sift down）操作，只是在进行元素比较时，不是直接比较元素大小，而是使用用户传入的comparator或者元素所属类的compareTo成员函数来比较大小。
private voidsiftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
Comparable<? super E> key =(Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>>1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, Ex) {
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;
}
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x){
Comparable<? super E> key =(Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; //assume left child is least
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>)c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}
@SuppressWarnings("unchecked")
private void siftDownUsingComparator(int k,E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E)queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c)<= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
五、增
在往PriorityQueue中添加元素（add/offer）PriorityQueue在队列满的时候，自动实现扩容。扩容的操作是privatevoid grow(int minCapacity)实现的，
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by50%
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);
}
add的实现就是调用offer，首先检查参数是否合法，PriorityQueue中不允许保存null元素；接下来检查队列是否已满，如果满了，执行grow，扩容；然后将元素放入队列数组，执行堆操作siftUp，当数组中不止一个元素时。
六、删
boolean remove(Object o)：删除对象o，首先利用indexOf(Object o)找到o的index，然后调用removeAt(private E removeAt(int i)):
privateE removeAt(int i) {
// assert i >= 0 && i <size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
如果不是最后一个对象，删除对象后，需要执行siftDown/siftUp操作。
同样的，poll操作是删除堆的根元素，即队列的queue[0]元素，
public Epoll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
//如果s==0，则说明此次删除了队列里的最后一个元素，
//删除后，队列为空，无需执行siftDown
if (s != 0)
siftDown(0, x);
return result;
}
七、查
peek()：返回队列queue中index=0的元素，queue[0]；如果为空，则返回null。
contains(Object o)：
public booleancontains(Object o) {
return indexOf(o) != -1;
}
总结：
（1） PriorityQueue实现可以作为学习堆数据结构的范例；
（2） PriorityQueue还有一个内部类private finalclass Itr，实现了迭代器；