java中的PriorityQueue底层和实现原理深入源码探究_java优先级队列源码看不了

前言

关于队列的一些前沿知识可看我之前的文章
【数据结构】栈和队列详细分析（全）

关于这个PriorityQueue，最主要是刷leetcode的时候了解到，所以就去挖源码以及网上的知识点

1. 定义

通过优先队列的源码可以知道一些基本的属性以及函数的使用方法
而优先队列的结构本身是二叉堆（大顶堆或者小顶堆）
具体插入元素的时候保持平衡保持有序。
优先级队列使用二叉堆的特点，可以使得插入的数据自动排序（升序或者是降序）。

示例一个简单例子：

public class Main {
    public static void main(String[] args) {
        Queue<Integer> que = new PriorityQueue<>();
        // 添加3个元素到队列:
        que.offer(1);
        que.offer(3);
        que.offer(2);
        System.out.println(que.poll()); // 1
        System.out.println(que.poll()); // 2
        System.out.println(que.poll()); // 3

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

通过结果可以得知，输出的结果是按照顺序输出

这是因为放入PriorityQueue的元素，必须实现Comparable接口，PriorityQueue会根据元素的排序顺序决定出队的优先级。本身默认是有一个比较器

如果要比较的对象没有比较器，则会通过重写的形式进行构造
具体如下：
关于这部分的代码主要参考链接如下：
使用PriorityQueue

public class Main {
    public static void main(String[] args) {
        Queue<User> q = new PriorityQueue<>(new UserComparator());
        // 添加3个元素到队列:
        q.offer(new User("Bob", "A1"));
        q.offer(new User("Alice", "A2"));
        q.offer(new User("Boss", "V1"));
        System.out.println(q.poll()); // Boss/V1
        System.out.println(q.poll()); // Bob/A1
        System.out.println(q.poll()); // Alice/A2
        System.out.println(q.poll()); // null,因为队列为空
    }
}

class UserComparator implements Comparator<User> {
    public int compare(User u1, User u2) {
        if (u1.number.charAt(0) == u2.number.charAt(0)) {
            // 如果两人的号都是A开头或者都是V开头,比较号的大小:
            return u1.number.compareTo(u2.number);
        }
        if (u1.number.charAt(0) == 'V') {
            // u1的号码是V开头,优先级高:
            return -1;
        } else {
            return 1;
        }
    }
}

class User {
    public final String name;
    public final String number;

    public User(String name, String number) {
        this.name = name;
        this.number = number;
    }

    public String toString() {
        return name + "/" + number;
    }
}
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

2. 源码

• 基于优先级堆的无界优先级队列。（简单来说，就是插入数据的时候会自动排序）
  优先队列的元素根据它们的自然顺序排序，或者由队列构造时提供的Comparator排序，这取决于使用的构造函数。
• 优先队列不允许空元素。
  依赖于自然排序的优先队列也不允许插入不可比较的对象(这样做可能会导致ClassCastException)。
• 这个队列的头是相对于指定的顺序来说最小的元素。
  如果多个元素被绑定为最小值，头部就是这些元素之一——绑定被任意打破。 队列检索操作轮询、删除、查看和元素访问队列头部的元素。
• 优先队列是无界的
  但是有一个内部容量来控制用于存储队列元素的数组的大小。 它总是至少和队列大小一样大。 随着元素被添加到优先队列中，其容量会自动增长。 未指定增长策略的详细信息。

通过查看其源码，其优先级队列的继承：

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

属性值：

@java.io.Serial
//序列号
private static final long serialVersionUID = -7720805057305804111L;

//默认初始化容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;

//优先级队列表示为一个平衡的二进制堆:queue[n]的两个子队列是queue[2*n+1]和queue[2*(n+1)]。 
//对于堆中的每个节点n和n的每个后代节点d, n <= d。如果队列非空，值最小的元素在队列[0]中。
transient Object[] queue; // non-private to simplify nested class access

//优先队列中的元素数。
int size;

//比较器，如果优先队列使用元素的自然顺序则为null。  
private final Comparator<? super E> comparator;

//这个优先队列在结构上被修改的次数
transient int modCount;     // non-private to simplify nested class access
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

构造方法的参数：

• public PriorityQueue()
  使用默认的初始容量(11)创建一个PriorityQueue，根据元素的自然顺序对其进行排序。
• public PriorityQueue(int initialCapacity)
  使用指定的初始容量创建一个PriorityQueue，根据元素的自然顺序对其进行排序。
• public PriorityQueue(Comparator<? super E> comparator)
  使用默认的初始容量创建一个PriorityQueue，其元素根据指定的比较器排序。
  参数:
  比较器——用来对优先队列排序的比较器。 如果为空，则使用元素的自然顺序。
• public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
  使用指定的初始容量创建一个PriorityQueue，根据指定的比较器对其元素进行排序。
• public PriorityQueue(Collection<? extends E> c)
  指定的集合是SortedSet或另一个PriorityQueue的实例，那么这个优先队列将按照相同的顺序排序。 否则，优先队列将按照其元素的自然顺序排序。
• public PriorityQueue(PriorityQueue<? extends E> c)
  优先队列将按照与给定优先队列相同的顺序排序
• public PriorityQueue(SortedSet<? extends E> c)
  优先队列将按照与给定排序集相同的顺序排序。

其源码部分展示如下：

常用方法：

2.1 添加元素add

• 增加元素add

查看其源码具体如下：
调用了offer函数

 public boolean add(E e) {
        return offer(e);
    }
1
2
3

其offer的函数如下：
将其madcount的数量加1，如果加1之后，尺寸超出载进行扩容

public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        siftUp(i, e);
        size = i + 1;
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11

具体增加的函数载siftUp函数，我们再看看这个函数的源码：
其只是比较了有没有使用自已的比较器，关键的添加在比较器中

 private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x, queue, comparator);
        else
            siftUpComparable(k, x, queue);
    }
1
2
3
4
5
6

具体比较器的内容如下：

    private static <T> void siftUpComparable(int k, T x, Object[] es) {
        Comparable<? super T> key = (Comparable<? super T>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = es[parent];
            if (key.compareTo((T) e) >= 0)
                break;
            es[k] = e;
            k = parent;
        }
        es[k] = key;
    }

    private static <T> void siftUpUsingComparator(
        int k, T x, Object[] es, Comparator<? super T> cmp) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = es[parent];
            if (cmp.compare(x, (T) e) >= 0)
                break;
            es[k] = e;
            k = parent;
        }
        es[k] = x;
    }
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

2.2 删除元素remove

源码如下：

    public boolean remove(Object o) {
        int i = indexOf(o);
        if (i == -1)
            return false;
        else {
            removeAt(i);
            return true;
        }
    }
1
2
3
4
5
6
7
8
9

其删除元素载removeAt函数中

    E removeAt(int i) {
        // assert i >= 0 && i < size;
        final Object[] es = queue;
        modCount++;
        int s = --size;
        if (s == i) // removed last element
            es[i] = null;
        else {
            E moved = (E) es[s];
            es[s] = null;
            siftDown(i, moved);
            if (es[i] == moved) {
                siftUp(i, moved);
                if (es[i] != moved)
                    return moved;
            }
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

删除操作同样也是siftDown或者是siftUp函数中，点开这个函数，同样也是通过比较器之后核心代码都在这一块区域中

    private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
        // assert n > 0;
        Comparable<? super T> key = (Comparable<? super T>)x;
        int half = n >>> 1;           // loop while a non-leaf
        while (k < half) {
            int child = (k << 1) + 1; // assume left child is least
            Object c = es[child];
            int right = child + 1;
            if (right < n &&
                ((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
                c = es[child = right];
            if (key.compareTo((T) c) <= 0)
                break;
            es[k] = c;
            k = child;
        }
        es[k] = key;
    }

    private static <T> void siftDownUsingComparator(
        int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
        // assert n > 0;
        int half = n >>> 1;
        while (k < half) {
            int child = (k << 1) + 1;
            Object c = es[child];
            int right = child + 1;
            if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
                c = es[child = right];
            if (cmp.compare(x, (T) c) <= 0)
                break;
            es[k] = c;
            k = child;
        }
        es[k] = x;
    }
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

2.3 队列头peek

源码如下：

public E peek() {
        return (E) queue[0];
    }
1
2
3

2.4 对象索引

private int indexOf(Object o) {
        if (o != null) {
            final Object[] es = queue;
            for (int i = 0, n = size; i < n; i++)
                if (o.equals(es[i]))
                    return i;
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9

3. 实战演示

通过lettcode的代码也可运用
比如计算丑数
题目：
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

1 是丑数。
n 不超过1690。

可以使用如下代码：

class Solution {
    public int nthUglyNumber(int n) {
        int[] factors = {2, 3, 5};
        Set<Long> seen = new HashSet<Long>();
        PriorityQueue<Long> heap = new PriorityQueue<Long>();
        seen.add(1L);
        heap.offer(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long curr = heap.poll();
            ugly = (int) curr;
            for (int factor : factors) {
                long next = curr * factor;
                if (seen.add(next)) {
                    heap.offer(next);
                }
            }
        }
        return ugly;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

默认是小顶堆：PriorityQueue<Integer> queue = new PriorityQueue<>();

改写大顶堆：

PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
});
1
2
3
4
5
6

简化的版本：PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2)->o2.compareTo(o1));