刷算法不知道PriorityQueue?看了这篇文章才知道他有多
最近在刷力扣题的时候不止一次看到过这个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、数据结构
优先级队列底层的数据结构其实是一颗二叉堆,什么是二叉堆呢?我们来看看
image在这里我们会发现以下特征:
(1)二叉堆是一个完全二叉树
(2)根节点总是大于左右子节点(大顶堆),或者是小于左右子节点(小顶堆)。
如果我们要插入一个节点怎么办呢?
image自己使用画图工具画的,能看懂就行,不要在意那些细节兄弟。过程如下:
(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<? extends E> c)
创建包含指定 collection 中元素的 PriorityQueue
。
(3)指定初始容量:PriorityQueue(int initialCapacity)
使用指定的初始容量创建一个 PriorityQueue
,并根据其自然顺序对元素进行排序。
(4)指定初始容量和比较器:PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
使用指定的初始容量创建一个 PriorityQueue
,并根据指定的比较器对元素进行排序。
(5)包含优先级元素:PriorityQueue(PriorityQueue<? extends E> c)
创建包含指定优先级队列元素的 PriorityQueue
。
(6)包含set元素:PriorityQueue(SortedSet<? extends E> 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、会员项目
会员的优先级总是比普通会员高,因此我们就可以使用优先级队列保存会员的优先级。
这里只给出俩。其他的各位同僚自己体会吧,我自己曾经使用优先级队列来保存无人机的各种状态信息。所以也可以保存各种状态信息。
微信图片_20200105134941.jpg