Java中PriorityQueue相关

优先队列：依靠堆数据结构来实现，因为堆又是完全二叉树，采用数组来存储，父子关系依靠下标来维系。

Java中，如果调用无参构造函数，默认生成一个能够容纳11个元素的数组，如果不指定比较器，按照小根堆来排列。

扩容操作：PriorityQueue的扩容选择和ArrayList(扩大到原来容量的1.5倍)，Vector(默认扩容到原容量的2倍，如果指定了扩容大小，就扩容指定大小)的策略都不同，PriorityQueue的扩容策略：如果当前数组容量小于64，就扩容到原来容量的2倍+2， 如果数组容量大于64， 就扩容到原来的1.5倍。

因为涉及到比较操作，所以在构造的时候允许传入一个比较器，如果传入比较器，就用传入的比较器来比较两个元素的大小，如果没有传入比较器，就用数组元素自己的比较器来比较。

堆的基本调整操作：siftUp(int k, E x), siftDown(int k, E x)

向上调整函数siftUp(int k, E x): 从当前位置开始，一直和父节点比较，如果小于父节点，就将父节点移到当前位置，然后将当前位置上移到父节点位置，接着和父节点进行比较，直到大于父节点或者当前位置移动到根节点，结束。

向下调整函数siftDown(int k, E x):只有待调整节点不是叶子节点的时候，才有调整的必要，如果是叶子节点，不需要调整。

类似于向上调整，向下调整的过程中，当前位置和孩子节点中小的一个进行比较，如果孩子节点更小，则将孩子节点上提作为父节点，当前位置下移到孩子节点的位置，接着和孩子节点中小的一个进行比较，直到当前节点小于两个孩子节点或者已经到达了叶子节点，结束。

调整过程中， half = size >>>1; (逻辑右移操作符：高位补0)，因为数组下标是从0开始的，half代表的就是第一个叶子节点的下标，调整过程都是在非叶子节点上进行的，所以结束条件就是while(k < half)。

调整操作heapify():数组中元素初始状态可能并不满足堆的要求，就需要进行调整，调整的策略非常简单，从最后一个非叶子节点开始调用siftDown,一直到根节点，调整操作完成。所以说调整操作还是在siftDown()基础上。源码：

一个需要特别注意的地方：删除特定对象的remove()函数，因为要维持堆的特性，在删除元素以后，将数组的最后一个元素放到删除位置，然后进行调整。在调整过程中就有两种情况：1.删除位置和最后一个元素都在根节点的同一棵子树上，则进行向下调整即可(siftDown); 2.如果不在根节点的同一棵子树上，则大小关系不确定，不一定是向上调整(siftUp)还是向下调整(siftDown), 先向下调整，调整完成以后如果还是原地，尝试进行向上调整，如果需要向上调整，就会出现最后一个元素被调整到删除位置的前面。为了区分这两种情况，remove()采取的策略是根据返回值来判断，如果返回null,则说明最后一个元素经过调整以后位于删除位置的后面，如果返回的是一个元素值，则说明最后一个元素被调整到了删除位置的前面。

经过上面的描述，就会发现一个问题，如果执行删除操作以后，最后一个元素被调整到了删除位置前面，那么迭代器的遍历操作就有可能漏掉这个元素，Java中解决的办法就是提供了一个额外的数据结构：双端队列forgetMeNot，将所有这种情况的元素都放入到forgetMeNot中，遍历过程中，遍历到数组末尾，还需要检查forgetMeNot是否为空，不为空的话还需要对forgetMeNot进行遍历。