java集合类库学习记录———PriorityQueue

1.特点

优先级队列的元素按照其自然顺序进行排序，或者根据构造队列时提供的 Comparator进行排序，具体取决于所使用的构造方法。

优先级队列不允许使用 null 元素。这是目前看到的第一个不允许放入null的集合。

优先级队列的内部结构是一个数组构成的最小堆（从0下标开始）。不了解堆数据结构的可以看数据结构与算法。

方法 iterator()中提供的迭代器不 保证以任何特定的顺序遍历优先级队列中的元素。如果需要按顺序遍历，请考虑使用Arrays.sort(pq.toArray())。

2.AbstractQueue

优先队列继承了AbstractQueue抽象类

AbstractQueue类提供某些 Queue操作的骨干实现。此类中的实现适用于基本实现不 允许包含null 元素时。（实现AbstractQueue类的集合都不允许插入null元素）。

add、remove 和 element 方法分别基于 offer、poll 和peek 方法。

3.源码解析

PriorityQueue中有4个地方值得关注：1.构造函数 2.上浮和下沉 3.删除操作 4.迭代器

1.构造函数

    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }

    public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }

    public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
        // Note: This restriction of at least one is not actually needed,
        // but continues for 1.5 compatibility
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }

    public PriorityQueue(Collection<? extends E> c) {		//判断集合类型并转去相应的初始化函数
        if (c instanceof SortedSet<?>) {
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();
            initElementsFromCollection(ss);
        }
        else if (c instanceof PriorityQueue<?>) {
            PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
            this.comparator = (Comparator<? super E>) pq.comparator();
            initFromPriorityQueue(pq);
        }
        else {
            this.comparator = null;
            initFromCollection(c);
        }
    }

    public PriorityQueue(PriorityQueue<? extends E> c) {	
        this.comparator = (Comparator<? super E>) c.comparator();
        initFromPriorityQueue(c);
    }

    public PriorityQueue(SortedSet<? extends E> c) {         this.comparator = (Comparator<? super E>) c.comparator();         initElementsFromCollection(c);     }

    private void initFromPriorityQueue(PriorityQueue<? extends E> c) { //利用一个优先队列初始化优先队列         if (c.getClass() == PriorityQueue.class) {             this.queue = c.toArray();             this.size = c.size();         } else {             initFromCollection(c);         }     }

    private void initElementsFromCollection(Collection<? extends E> c) { //利用SortedSet初始化优先队列
        Object[] a = c.toArray();					//返回从小到大的顺序的数组也是符合最小堆的规则的
        // If c.toArray incorrectly doesn't return Object[], copy it.
        if (a.getClass() != Object[].class)
            a = Arrays.copyOf(a, a.length, Object[].class);
        int len = a.length;
        if (len == 1 || this.comparator != null)
            for (int i = 0; i < len; i++)
                if (a[i] == null)
                    throw new NullPointerException();
        this.queue = a;
        this.size = a.length;
    }

    private void initFromCollection(Collection<? extends E> c) {	//其他集合初始化
        initElementsFromCollection(c);
        heapify();							//构建堆
    }

    private void heapify() {					//从堆的前一半（高度为2的堆）开始下沉每个元素，构建最小堆
        for (int i = (size >>> 1) - 1; i >= 0; i--)
            siftDown(i, (E) queue[i]);
    }

构造函数一共分为两种方式：1.通过指定初始容量和比较器来创建一个空的优先队列。2.通过传入一个集合来初始化优先队列。（图片来自于http://blog.csdn.net/u011518120/article/details/53022406），图中红色代表私有方法，绿色代表公有方法。还有在右图中少画了initFromCollection方法底层也是用initElementsFromCollection方法实现的。

2.上浮和下沉

    private void siftUp(int k, E x) {	//在指定位置k上插入元素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) {			//当x元素比父节点元素小时，上浮x到父节点
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

   private void siftDown(int k, E x) {	//在指定位置k上插入元素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;       
        while (k < half) {
            int child = (k << 1) + 1; // 默认child为左节点
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right]; //当右节点存在且比左节点小时，child为右节点
            if (key.compareTo((E) c) <= 0)
                break;
            queue[k] = c;	         //当元素x比child大时，下沉x
            k = child;
        }
        queue[k] = key;
    }

3.删除操作

    public boolean remove(Object o) {		//当传入参数引用和数组中的元素equals时，调用removeAt方法删除
        int i = indexOf(o);
        if (i == -1)
            return false;
        else {
            removeAt(i);
            return true;
        }
    }

    boolean removeEq(Object o) {		//当传入参数引用和数组中的元素指向同一对象而非equals时，调用removeAt方法删除
        for (int i = 0; i < size; i++) {
            if (o == queue[i]) {
                removeAt(i);
                return true;
            }
        }
        return false;
    }

    private E removeAt(int i) {			
        // assert i >= 0 && i < size;
        modCount++;
        int s = --size;
        if (s == i) 			//如果删除的是最后一个元素，直接删除
            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)	//如果新子堆中的最小值小于父堆时，则这个元素在迭代过程中remove操作时会被跳过，需要在迭代器中保存起来
                    return moved;
            }
        }
        return null;
    }

核心的removeAt方法的过程见下图：（图片来自于：http://blog.csdn.net/hxpjava1/article/details/21478323）

4.迭代器

   private final class Itr implements Iterator<E> {
        /**
         * Index (into queue array) of element to be returned by
         * subsequent call to next.
         */
        private int cursor = 0;			//指向当前元素

        /**
         * Index of element returned by most recent call to next,
         * unless that element came from the forgetMeNot list.
         * Set to -1 if element is deleted by a call to remove.
         */
        private int lastRet = -1;		//指向上一次next的元素（非遗漏集合中）

        /**
         * A queue of elements that were moved from the unvisited portion of
         * the heap into the visited portion as a result of "unlucky" element
         * removals during the iteration.  (Unlucky element removals are those
         * that require a siftup instead of a siftdown.)  We must visit all of
         * the elements in this list to complete the iteration.  We do this
         * after we've completed the "normal" iteration.
         *
         * We expect that most iterations, even those involving removals,
         * will not need to store elements in this field.
         */
        private ArrayDeque<E> forgetMeNot = null;	//	被遗漏元素的集合

        /**
         * Element returned by the most recent call to next iff that
         * element was drawn from the forgetMeNot list.
         */
        private E lastRetElt = null;			//      被遗漏集合中上次调用next时返回的元素

        /**
         * The modCount value that the iterator believes that the backing
         * Queue should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        private int expectedModCount = modCount;

        public boolean hasNext() {			// 迭代操作时，当迭代完数组还要迭代被遗漏元素的集合
            return cursor < size ||
                (forgetMeNot != null && !forgetMeNot.isEmpty());
        }

        @SuppressWarnings("unchecked")
        public E next() {
            if (expectedModCount != modCount)
                throw new ConcurrentModificationException();
            if (cursor < size)					//迭代数组
                return (E) queue[lastRet = cursor++];
            if (forgetMeNot != null) {				//迭代被遗漏元素集合
                lastRet = -1;					//辅助remove方法标记
                lastRetElt = forgetMeNot.poll();
                if (lastRetElt != null)
                    return lastRetElt;
            }
            throw new NoSuchElementException();
        }

        public void remove() {
            if (expectedModCount != modCount)
                throw new ConcurrentModificationException();
            if (lastRet != -1) {				//当上次next使用的是非遗漏集合时，删除操作如果产生了遗漏元素则加入到遗漏集合中
                E moved = PriorityQueue.this.removeAt(lastRet);
                lastRet = -1;
                if (moved == null)
                    cursor--;
                else {
                    if (forgetMeNot == null)
                        forgetMeNot = new ArrayDeque<>();
                    forgetMeNot.add(moved);
                }
            } else if (lastRetElt != null) {			//当上次next使用的时遗漏集合时，在堆中删除遗漏元素（在遗漏集合中的此元素在next方法中已经删除过了）
                PriorityQueue.this.removeEq(lastRetElt);
                lastRetElt = null;
            } else {
                throw new IllegalStateException();
            }
            expectedModCount = modCount;
        }
    }

“遗漏”元素是怎么产生的： 在迭代过程中，我们除了用迭代器的remove方法外，不能做出其他修改集合结构的操作。但是当迭代到某个元素执行迭代器删除时，会删除前一个元素（上次next返回的元素）。所以可能会产生最后一个元素上移到迭代器的上方，导致迭代器不能访问，遗漏元素就产生了。

向上图，如果迭代器在迭代到35的时候使用remove方法，则元素24就被遗漏了。所以要把它加入遗漏集合中。