文档章节

PriorityQueue源码分析

Hosee
 Hosee
发布于 2015/12/15 11:21
字数 1362
阅读 535
收藏 3

3 月,跳不动了?>>>

PriorityQueue是从JDK1.5开始提供的新的数据结构接口,它是一种基于 优先级堆的极大优先级队列。优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。如果不提供Comparator的话,优先队列中元素默认按自然顺序排列,也就是数字默认是小的在队列头,字符串则按字典序排列,也可以根据 Comparator 来指定,这取决于使用哪种构造方法。优先级队列不允许 null 元素。依靠自然排序的优先级队列还不允许插入不可比较的对象(这样做可能导致 ClassCastException)

优先级队列是无界的,但是有一个内部容量,控制着用于存储队列元素的数组大小。它通常至少等于队列的大小。随着不断向优先级队列添加元素,其容量会自动增加。无需指定容量增加策略的细节。

我们从源码的角度来看看PriorityQueue是如何实现的。

建堆:

PriorityQueue内部的数组声明如下:

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.
     */
 private transient Object[] queue;

我们发现queue前面使用了关键字transient,这是为什么呢?

PriorityQueue的默认长度为11,而且PriorityQueue是会扩容的

/**
     * Increases the capacity of the array.
     *
     * @param minCapacity the desired minimum capacity
     */
    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);

所以大多数情况下,真实数据的大小都小于数组的queue实际大小,如果将整个queue都序列化,那有很多空间是浪费的。所以PriorityQueue自己实现了writeObject与readObject来提高性能。(关于对象的序列化请查看这里

PriorityQueue初始化过程和最大堆的建堆过程基本上一样的(想了解建堆过程请查看排序篇的堆排),从有子节点的最靠后元素开始往前,每次都调用siftDown方法来调整。这个过程也叫做heapify。

当然,只有当你想将现有的数据转成PriorityQueue时才需要建堆,在空的PriorityQueue中add新元素时只是一个调整的过程

/**
     * Creates a {@code PriorityQueue} containing the elements in the
     * specified collection.  If the specified collection is an instance of
     * a {@link SortedSet} or is another {@code PriorityQueue}, this
     * priority queue will be ordered according to the same ordering.
     * Otherwise, this priority queue will be ordered according to the
     * {@linkplain Comparable natural ordering} of its elements.
     *
     * @param  c the collection whose elements are to be placed
     *         into this priority queue
     * @throws ClassCastException if elements of the specified collection
     *         cannot be compared to one another according to the priority
     *         queue's ordering
     * @throws NullPointerException if the specified collection or any
     *         of its elements are null
     */
    @SuppressWarnings("unchecked")
    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);
        }
    }
PriorityQueue支持将Collection类型直接转成 PriorityQueue。

建堆过程:

private void heapify() {
        for (int i = (size >>> 1) - 1; i >= 0; i--)
            siftDown(i, (E) queue[i]);
    }

private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }

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

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

添加新元素的过程如下:

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

每次添加新的元素进来实际上是在数组的最后面增加。在增加这个元素的时候就有了判断数组长度和调整的一系列动作。等这些动作调整完之后就要进行siftUp方法调整。这样做是为了保证堆原来的性质。

其他:

1. 此实现不是同步的。不是线程安全的。如果多个线程中的任意线程从结构上修改了列表, 则这些线程不应同时访问 PriorityQueue 实例,这时请使用线程安全的PriorityBlockingQueue 类。

2. 此实现为offer、poll、和 add 方法提供 O(logn) 时间;为 remove(Object) 和 contains(Object) 方法提供O(n)时间;为检索方法(peek、element 和 size)提供O(1)。

3. 方法iterator()中提供的迭代器并不保证以有序的方式遍历优先级队列中的元素。因为最小堆只能保证根结点是最小,不能保证整体都有序。

Reference:

1. http://cuisuqiang.iteye.com/blog/2019157

2. http://shmilyaw-hotmail-com.iteye.com/blog/1827136

3. http://zhidao.baidu.com/link?url=jJlf0fLjuv6Y0OjvvQqLo46PhAMdVTHau9NkmHpBYgDBDAtlBnUJrtUfDxS22ftpeR9su6m6n85K6X8W7FpvO_

© 著作权归作者所有

Hosee
粉丝 621
博文 135
码字总数 209956
作品 0
杭州
程序员
私信 提问
加载中

评论(0)

Java集合--Queue(Java中实现1)

1.2 Java中的实现 上一篇,阐述了队列的实现结构,通过图片的形式让大家有了更进一步的了解。 接下来,我,我们来看看队列在Java具体是如何成仙了,来看下Queue的代码!!! 在Java中,Array...

贾博岩
2017/10/21
0
0
并发容器学习—DelayQueue与PriorityBlockingQueue

一、DelayQueue并发容器 1.DelayQueue的底层实现 DelayQueue是一个线程安全且无界的阻塞队列,只有在延迟时间满足后才能获取队列中的元素,因此队列中的元素必须实现Delay接口,在创建元素时...

宁听
2019/05/02
32
0
学习PriorityQueue源码

本来想先看看DelayQueue,结果里面用到了PriorityQueue,所以先学习一下PriorityQueue的编码逻辑。 基于优先级堆的无界优先级队列。优先级队列的元素根据其自然顺序排序,或者由队列构造时提...

woshixin
2018/10/10
24
0
《k8s-1.13版本源码分析》-抢占调度

源码分析系列文章已经开源到github,地址如下: github: https://github.com/farmer-hutao/k8s-source-code-analysis gitbook: https://farmer-hutao.github.io/k8s-source-code-analysis ......

CloudGeek
2019/03/29
0
0
Java 优先队列 PriorityQueue PriorityBlockingQueue 源码分析

基本使用 输出 PriorityQueue 成员变量 通过数组实现一个堆,元素在queue数组中并不是完全有序的,仅堆顶元素最大或最小。 基本方法 以poll方法为例,实际上是获取堆顶元素,然后调整堆。 调...

被称为L的男人
2019/01/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

pygame---2048

用4*4的二维数组保存地图,pygame.key.get_pressed()获取键盘操作 import randomimport sysimport pygamefrom pygame.locals import *PIXEL=150SCORE_PIXEL=100SIZE=4#地图...

ivyhaha
今天
11
0
机器学习算法(五)—— 最优化方法:梯度下降

一、什么是梯度下降 梯度下降是迭代法的一种,可以用于求解最小二乘问题(线性和非线性都可以)。 在求解机器学习算法的模型参数,即无约束优化问题时,梯度下降(Gradient Descent)是最常采用...

筠初
今天
24
0
Java并发编程(03):多线程并发访问,同步控制

本文源码:GitHub·点这里 || GitEE·点这里 一、并发问题 多线程学习的时候,要面对的第一个复杂问题就是,并发模式下变量的访问,如果不理清楚内在流程和原因,经常会出现这样一个问题:线...

知了一笑
今天
27
0
MyBatis-Spring:整合Mybatis与Spring方式二:SqlSessionDaoSupport

本文上接《MyBatis-Spring:整合Mybatis与Spring方式一:SqlSessionTemplate》, SqlSessionDaoSupport是一个抽象的支持类,用来为你提供SqlSession。调用getSqlSession()方法你会得到一个Sql...

明德君
今天
141
0
count(1)、count(*)与count(列名)的执行区别

执行效果: 1. count(1) and count(*) 当表的数据量大些时,对表作分析之后,使用count(1)还要比使用count(*)用时多了! 从执行计划来看,count(1)和count(*)的效果是一样的。 但是在表做过分...

七宝1
今天
16
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部