美文网首页
PriorityQueue源码分析

PriorityQueue源码分析

作者: 言西枣 | 来源:发表于2016-05-18 23:33 被阅读342次

源码来自jdk1.8


PriorityQueue内部由最小堆实现,也就是说每次执行add或是remove之后,总是让最小的元素移动到根,但是,使用迭代器进行访问时,不会保证一个递增的顺序。

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

为了维持最小堆,队列的元素类型必须实现Comparable接口,或者是在构造队列的时候提供一个元素类型的比较器(Comparator),所以元素不能为空。

队列的访问操作poll, remove, peek, and element访问的是队头元素,在这里也就是根元素,也就是最小的元素。

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {

    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    /**
     * Priority queue represented as a balanced binary heap: the two
     * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
     * priority queue is ordered by comparator, or by the elements'
     * natural ordering, if comparator is null: For each node n in the
     * heap and each descendant d of n, n <= d.  The element with the
     * lowest value is in queue[0], assuming the queue is nonempty.
     */
    transient Object[] queue; // non-private to simplify nested class access

    /**
     * The number of elements in the priority queue.
     */
    private int size = 0;

    /**
     * The comparator, or null if priority queue uses elements'
     * natural ordering.
     */
    private final Comparator<? super E> comparator;

    /**
     * The number of times this priority queue has been
     * <i>structurally modified</i>.  See AbstractList for gory details.
     */
    transient int modCount = 0; // non-private to simplify nested class access
    // 省略了方法
}

这里用了一个Object[]来存放元素,queue[n] 的孩子节点是 queue[2*n+1] 和 queue[2*(n+1)]

构造函数

PriorityQueue的构造函数大致分为两类,一种是确定数组初始化大小和Comparator,另一种是由Collection对象构造

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);
        }
    }

可以看到SortedSet和PriorityQueue这两种在构造的时候可以获取Comparator(也可能获取不到,因为是自然排序),其余的都是直接构造,如果这个对象没有实现Comparable接口,那么在使用的时候就会产生一个ClassCastException

add/offer

public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }

add通过offer实现。这个函数干了这几件事情:检查为空,增加修改次数,需要的情况下扩展,增加大小,赋值,向上调整堆,返回真。
这里的关键是SiftUp函数

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;
    }

将要插入的节点与父节点进行比较,如果更小,就将父节点往下,然后继续向上比较,如果大于等于,就放在当前的位置。

remove()/poll()

注意这里是无参remove,通过poll实现

public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        E result = (E) queue[0];
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
            siftDown(0, x);
        return result;
    }

删除并返回最小的队头元素后,将数组末位的元素放到队头,然后SiftDown,基本于上面相反。

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;
    }

将要插入的节点与两个子节点进行比较,如果小于两个子节点,那么就放在当前位置,如果大于子节点,就将较小的子节点与插入节点交换,然后在新的位置继续向下调整,直到这个新的节点同时小于两个子节点或者它达到了一个叶节点的位置。

相关文章

网友评论

      本文标题:PriorityQueue源码分析

      本文链接:https://www.haomeiwen.com/subject/mdwwrttx.html