PriorityQueue：一个提升你刷题效率和解决工作难题的集合框架（基于jdk1.8源码分析）

最近在刷力扣题的时候不止一次看到过这个PriorityQueue，他的优良特性可以帮助我们解决大量的题目。这篇文章从用法、原理、源码以及力扣实际题目的角度进行一个全面的分析。希望对你有帮助。

一、什么是优先级队列

1、概念

我们都知道队列，队列的核心思想就是先进先出，这个优先级队列有点不大一样。优先级队列中，数据按关键词有序排列，插入新数据的时候，会自动插入到合适的位置保证队列有序。（顺序有两种形式：升序或者是降序）

来一个标准点的定义：

PriorityQueue类在Java1.5中引入。PriorityQueue是基于优先堆的一个***队列，这个优先队列中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化的时排序。
要求使用Java Comparable和Comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素。

比如我们往队列里面插入132，插入2的时候，就会在内部调整为123（默认顺序是升序）。正是由于这个优良特性可以帮助我们实现一系列问题。我们先看一个例子，体会一下他的优点，然后再看一下为什么能够实现这样的功能。

//测试优先级队列自动排序
public static List<Integer> insertSort(){
    List<Integer> list = new ArrayList<Integer>();
    Queue<Integer> queue = new PriorityQueue<Integer>(7);
    Random random = new Random();
    for(int i=0;i<7;i++){
        queue.add(new Integer(random.nextInt(100))); 
    }
    for(int i=0;i<queue.size();i++){
        list.add(queue.poll());
    }
    return list;
}
public static void main(String[] args) {
                   System.out.println(Arrays.toString(insertSort().toArray()));
}
//输出：2.5.16.78.92.97.99

我们看到就算是我们随意插入数据，但是输出的结果总是有序的，这样一来优先级队列就可以有了很多个使用场景。下面给出一道力扣题。体会一下他的优点。

2、案例演示特性

Leetcode215题：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

输入：3,2,3,1,2,4,5,5,6，k = 4。输出就是5，因此重复的并不考虑。我们一般情况下一般首先想到冒泡排序。每一次都冒出来一个最小的元素，这样冒K次，就是我们想要的结果。

public int findKthLargest(int[] nums, int k) {
        int s = 0;
        for(int i=0; i<nums.length-1; i++){
            for(int j=i+1; j<nums.length; j++){
                if(nums[i] > nums[j]){
                    int tmp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tmp;
                }
            }
            //冒了K次了，那就直接返回即可
            if(s++ >= k) break;
        }
        return nums[nums.length-k];
}

其实冒泡排序还可以解决另外一个问题，那就是返回倒数第K大的元素，方法是每次冒出来一个最大的元素即可。

这样做很简单，但是需要我们自己手写冒泡排序，下面我们看使用优先级队列如何解决的。

public int findKthLargest(int[] nums, int k) {
       Queue<Integer> queue = new PriorityQueue<>();
       for(int num : nums){ 
           queue.add(num);
           //当queue的大小大于k，每次弹出堆顶的最小元素；
           if(queue.size() > k) queue.poll();           
       }
       return queue.peek();
}

就这几行代码就搞定了，是不是超级简单。为什么优先级队列能够实现呢？下面我们来分析一下他的数据结构：

3、数据结构

优先级队列底层的数据结构其实是一颗二叉堆，什么是二叉堆呢？我们来看看

在这里我们会发现以下特征：

（1）二叉堆是一个完全二叉树

（2）根节点总是大于左右子节点（大顶堆），或者是小于左右子节点（小顶堆）。

如果我们要插入一个节点怎么办呢？

自己使用画图工具画的，能看懂就行，不要在意那些细节兄弟。过程如下：

（1）找到待插入位置：满足完全二叉树的特点，依次插入

（2）插入之后判断是否满足二叉堆的性质，不满足那就调整

（3）1<==>6交换，发现不满足，1<==>4交换，满足即停止。

对于我们的优先级队列就是这样的一种数据结构，因此我们在插入的时候保证了数据的有序性。

OK。到这基本上我们能够体会到优先级队列的思想了。来一个小结：

优先级队列使用二叉堆的特点，可以使得插入的数据自动排序（升序或者是降序）。

现在我们知道了这些，还没讲源码。从源码的角度来体会一下：

二、源码分析（基于jdk1.8）

源码分析一般的顺序都是先类属性、构造方法、普通方法。在编译器中鼠标定位到这个PriorityQueue上，ctrl+鼠标左键就可以进入到这个集合的源码里面。

1、属性

(1)默认初始容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
（2）维护一个队列：因为基于二叉堆来实现优先队列，queue[i]的子节点为queue[2*i+1]/queue[2*i+2];
transient Object[] queue; 
（3）优先级队列中的元素个数
private int size = 0;
（4）比较器：用于降序或者是比较自定义的对象，比如可以根据age
private final Comparator<? super E> comparator;
（5）优先级队列的结构：被修改的次数
transient int modCount = 0;

2、构造方法

（1）默认构造方法：PriorityQueue()

使用默认的初始容量（11）创建一个 PriorityQueue，并根据其自然顺序对元素进行排序。

（2）包含集合元素：PriorityQueue(Collection c)

创建包含指定 collection 中元素的 PriorityQueue。

（3）指定初始容量：PriorityQueue(int initialCapacity)

使用指定的初始容量创建一个 PriorityQueue，并根据其自然顺序对元素进行排序。

（4）指定初始容量和比较器：PriorityQueue(int initialCapacity, Comparator comparator)

使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器对元素进行排序。

（5）包含优先级元素：PriorityQueue(PriorityQueue c)

创建包含指定优先级队列元素的 PriorityQueue。

（6）包含set元素：PriorityQueue(SortedSet c)

创建包含指定有序 set 元素的 PriorityQueue。

3、普通方法

PriorityQueue中常用的方法很多。来看几个常用的。

（1）add：插入一个元素，不成功会抛出异常

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

我们看到add方法其实是通过调用offer方法实现的。我们直接看offer方法

（2）offer：插入一个元素，不能被立即执行的情况下会返回一个特殊的值（true 或者 false）

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

注意，优先级队列插入的元素不能为空，这一点在文章一开始提到过。步骤是这样的：

首先把modCount数量加1，如果容量不够把当前队列的尺寸加1，最后在i的位置上使用siftUp方法把e添加进来。此时真正插入的操作又落到了siftUp方法身上，我们接着看。

   private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

尼玛，这里也没有实现真正的插入操作，而是先判断是否使用了自己的比较器。我们直接来看自己的比较器不为空，如何插入。

    @SuppressWarnings("unchecked")
    private void siftUpUsingComparator(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (comparator.compare(x, (E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }

这里就是真正的插入操作了。一个正常的数据插入过程。没什么特别的。

（3）remove：删除一个元素，如果不成功会返回false。

    public boolean remove(Object o) {
        int i = indexOf(o);
        if (i == -1)
            return false;
        else {
            removeAt(i);
            return true;
        }
    }

这里会发现真正实现删除操作的是removeAt方法。我们跟进去看看

    @SuppressWarnings("unchecked")
    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);
            if (queue[i] == moved) {
                siftUp(i, moved);
                if (queue[i] != moved)
                    return moved;
            }
        }
        return null;
    }

这个删除操作主要是两部分，if里面判断删除的是否是最后一个，否则的话就是用siftDown方法进行“向下沉”删除。不成功那就使用“向上浮”。

    //将元素x存储在queue[k],并进行相应的调整
    private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }

删除的时候同样需要进行判断比较器。

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

OK。删除操作就是这么多。基本思路是向上浮还是向下沉。

（4）poll：删除一个元素，并返回删除的元素

   @SuppressWarnings("unchecked")
    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删除操作，就不赘述了。

（5）peek：查询队顶元素

    @SuppressWarnings("unchecked")
    public E peek() {
        return (size == 0) ? null : (E) queue[0];
    }

（6）indexOf(Object o)：查询对象o的索引

    private int indexOf(Object o) {
        if (o != null) {
            for (int i = 0; i < size; i++)
                if (o.equals(queue[i]))
                    return i;
        }
        return -1;
    }

（7）contain(Object o)：判断是否容纳了元素

    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

实现原理很简单和上面的一样。

OK，源码就是这些。

三、优先级队列使用

上面已经介绍了原理和源码。而且给出了一个实际力扣案例。但是那属于算法，其实在真正工作领域也有不少的应用场景。

1、股票交易

我们的股票屏幕上总是给出最好或者是表现最差的那些股票。就可以基于优先级队列。方法其实是和找出前K个最大最小的元素方法类似。可以类比到股票中。

这只是给出了一个案例，你可以把股票交易的这样的使用场景类比到其他的场景中去。

2、会员项目

会员的优先级总是比普通会员高，因此我们就可以使用优先级队列保存会员的优先级。

这里只给出俩。其他的各位同僚自己体会吧，我自己曾经使用优先级队列来保存无人机的各种状态信息。所以也可以保存各种状态信息。

一、什么是优先级队列

二、源码分析（基于jdk1.8）

三、优先级队列使用

更多相关文章

随机推荐