JDK1.8源码-12-PriorityQueue

字数统计: 2.6k字   |   阅读时长≈ 10分钟

JDK1.8源码-12-PriorityQueue

前序

写在前面：请把我的博客中关于 二叉堆的数据结构看了再来看此篇，效果会增倍！！！

之前的文章中，我们有介绍过动态数组ArrayList，双向队列LinkedList，键值对集合HashMap，树集TreeMap。

他们各自有各自的优点，

  • ArrayList动态扩容，数组实现查询非常快但要求连续内存空间
  • 双向队列LinkedList 不需要像ArrayList一样连续的内存空间，他们以链表的形式连接各个节点的，但是查询的效率特别低。
  • HashMap存放的是键值对，内部使用数组加链表的形式实现，检索快但是由于是按照Hash值进行存储，所以无序，在有些情况下不合适。
  • TreeMap 使用了优化的排序二叉树（红黑树）进行逻辑实现，物理实现使用一个静态内部类Entry 代表一个树节点，这是一个完全有序的结构，但是每个树节点都需要保存一个父节点的引用，左右孩子节点引用，还有一个value值，虽然效率高但是开销很大。

今天我们将要介绍的PriorityQueue优先队列，更多的可以理解为是上述所有集合实现的一种折中的结构，它逻辑上使用堆结构（完全二叉树实现），物理上使用动态数组实现，并非像TreeMap一样完全有序，但是如果按照指定方式出队，结果依然是有序的。本篇就将详细谈谈该结构的内部实现。

1. 构造函数

在实际介绍PriorityQueue原理之前，再次啰嗦PriorityQueue的内部结构。

  • PriorityQueue中的元素在逻辑上构成了一棵完全二叉树
  • PriorityQueue实际存储时是一个数组类型
  • PriorityQueue 继承了接口Queue ，表明这是一个队列，只是它并不像普通队列（如LinkedList）在遍历输出时候简单的按照顺序从头到尾输出
  • PriorityQueue 总是先输出根节点的值，然后调整树使它继续成为一棵完全二叉树，每次输出根节点总是整个树优先级最高的，要么数值最小要么数值最大。

在PriorityQueue的内部，主要有以下结构属性构成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 默认用于存储节点信息的数组大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;

// 用于存储节点信息的数组
transient Object[] queue;

// 数组中实际存放元素的个数
private int size = 0;

// 内部比较器
private final Comparator<? super E> comparator;

// 用于记录修改次数的变量
transient int modCount = 0;
  • 堆这种数据结构主要分为两种，大根堆和小根堆，而我们每次调整结构都是按照某种规则比较两个元素值的大小，然后调整堆的结构。，这里我们就需要用到比较器。（所以构建一个PriorityQueue 实例主要还是初始化数组容量和Comparator 比较器，而在PriorityQueue 中主要有以下几种构造器）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}
public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}

public PriorityQueue(int initialCapacity,Comparator<? super E> comparator) {
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}
  1. 主要构造器有上述四种，前三种在内部会调用最后一个构造器
  2. 两个参数：
    • 一个指定要初始化数组的容量，
    • 一个则用于初始化一个比较器
    • （如果没有显示的指定他们的值，默认初始化容量DEFAULT_INITIAL_CAPACITY（11), 比较器传入的是null）

下面我们看获取到PriorityQueue实例之后，如何向其中添加和删除节点却一样保持原堆结构不变。

2. 优先队列的增删改查

2.1 增加

add(E e) 和 offer(E e) 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 实际上add方法的内部调用的还是offer方法
    public boolean add(E e) {
        return offer(e);
    }

// 主要看看offer是如何实现添加一个元素到堆结构中并维持这种结构不被破坏的
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        // 首先收取queue中实际存放元素的个数
        int i = size;
        // 如果数组已经被完全使用了（没有空间了）
        // 调用grow方法进行扩容
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        // 接着判断该完全二叉树是否为空，
        // 如果没有任何节点，那么直接将新增节点作为根节点即可
        if (i == 0)
            queue[0] = e;
        else
            // 否则会调用siftUp添加新元素并调整结构，这个是整个插入最重点的地方
            siftUp(i, e);
        return true;
    }


	// 如果原数组较小则会扩大两倍
	// 否则增加百分之50
    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);
    }


    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
  • siftUp(int k, E x)
1
2
3
4
5
6
7
private void siftUp(int k, E x) {
    // 此处会根据调用者是否传入比较器而分为两种情况，代码类似，我们只看一种即可。
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        // 首先获取父节点的索引
        int parent = (k - 1) >>> 1;
        // 拿到父节点对应索引的值
        Object e = queue[parent];
        // 如果新增的节点值和父节点的值比较之后满足堆结构,就break直接返回
        if (comparator.compare(x, (E) e) >= 0)
            break;
        // 否则循环向上交换，最终完成堆结构的调整
        queue[k] = e;
        k = parent;
    }
    // 最后再换，优化了复杂度
    queue[k] = x;
}

具体我们通过一个实例演示整个过程：

mark

  • 首先初始化一个小根堆，加入我们现在要添加一个新元素的值是5，根据siftUpUsingComparator方法的代码，此时参数 k 是 6， 对应最后一个节点父元素的索引是 2 （即索引是2的节点），然后 e 的值就是11
  • 通过比较器判断5是否小于e , 如果小于则说明需要调整结构，那么将最后一个节点值用父节点e的值进行取代，也就是以下的流程。

mark

  • 再次进入循环，发现parent的值是 （2-1）/2=0 ,比较器比较索引是0的节点和我们需要的新插入的节点（值是5），发现3小于5，则break跳出循环
  • 最后将queue[k] = x

mark

2.2 删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
    public boolean remove(Object o) {
        int i = indexOf(o);
        if (i == -1)
            return false;
        else {
            removeAt(i);
            return true;
        }
    }

// 调用的是以下removeAt(i) 方法

    private E 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);
            // 调整完成之后，会判断queue[i] == moved
            if (queue[i] == moved) {
                siftUp(i, moved);
                if (queue[i] != moved)
                    return moved;
            }
        }
        return null;
    }

（如果向下调整过结构自然是不需要再向上调整了），如果queue[i] != moved值为true表示向上调整过结构，那么将会返回moved。（至于为什么要在向上调整结构之后返回moved，主要是用于迭代器使用，此处暂时不会介绍）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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;
}

2.3 有序出队

peek() poll()

  • PriorityQueue这种结构使用的是堆结构，所以它是一种不完全有序的结构，但是我们也提过，可以逐个出队来实现有序输出。下面我们看看它是如何实现的
  • peek( ) 获取队列的头元素
1
2
3
public E peek() {
    return (size == 0) ? null : (E) queue[0];
}
  • poll() 获取队列的头元素并出队
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public E poll() {
    
    // 首先判断该队中是否有元素
    if (size == 0)
        // 如果没有则直接返回null
        return null;
    int s = --size;
    modCount++;
    // 分别获取头元素和末节点的元素
    E result = (E) queue[0];
    E x = (E) queue[s];
    // 删除末节点的元素
    queue[s] = null;
    // 从0到x 向下调整堆结构
    if (s != 0)
        siftDown(0, x);
    return result;
}

下面我们看一个实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void main(String[] args) {
    PriorityQueue<Object> pq = new PriorityQueue<>();

    pq.offer(1);
    pq.offer(21);
    pq.offer(345);
    pq.offer(23);
    pq.offer(22);
    pq.offer(44);
    pq.offer(0);
    pq.offer(34);
    pq.offer(2);

    while (pq.peek()!=null){
        System.out.println(pq.poll() + " ");
    }
}

输出结果如下：

1
2
3
4
5
6
7
8
9
0 
1 
2 
21 
22 
23 
34 
44 
345

注意：

  • 这里我们没有显示的传入比较器，此处会默认使用Integer的Comparator（也就是从小到大：小根堆）
  • 如果我们需要实现大根堆，需要传递一个自定义比较器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void main(String[] args) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare (Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    pq.offer(1);
    pq.offer(21);
    pq.offer(345);
    pq.offer(23);
    pq.offer(22);
    pq.offer(44);
    pq.offer(0);
    pq.offer(34);
    pq.offer(2);

    while (pq.peek()!=null){
        System.out.println(pq.poll() + " ");
    }
}

输出结果如下：

1
2
3
4
5
6
7
8
9
345 
44 
34 
23 
22 
21 
2 
1 
0
打赏
  • 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！
  • © 2019-2022 Zhuuu
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信