Java - PriorityQueue 优先队列

发表于

Java - PriorityQueue 优先队列

最近遇到一道算法题，说难其实也不难，但是用之前的思路和知识总感觉很麻烦很耗时。在看高手解析时发现了一种新思路，即使用PriorityQueue来取最大值和最小值。在此记录。

题目描述

题目链接-牛客网

数据流中的中位数
描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
示例1
输入：
[5,2,3,4,1,6,7,0,8]
返回值：
"5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "
说明：
数据流里面不断吐出的是5,2,3…,则得到的平均数分别为5,(5+2)/2,3…
示例2
输入：
[1,1,1]
返回值：
"1.00 1.00 1.00 "

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* 大顶堆，存储左半边元素 */
private PriorityQueue<Integer> left =new PriorityQueue<>((o1, o2)-> o2 - o1);
/* 小顶堆，存储右半边元素，并且右半边元素都大于左半边 */
private PriorityQueue<Integer> right =new PriorityQueue<>();
/* 当前数据流读入的元素个数 */
private int N=0;
public void Insert(Integer val){
/* 插入要保证两个堆存于平衡状态 */
if(N%2==0){
        /* N 为偶数的情况下插入到右半边。
         * 因为右半边元素都要大于左半边，但是新插入的元素不一定比左半边元素来的大，
         * 因此需要先将元素插入左半边，然后利用左半边为大顶堆的特点，取出堆顶元素即为最大元素，此时插入右半边 */
        left.add(val);
        right.add(left.poll());
    }else{
        right.add(val);
        left.add(right.poll());
    }
    N++;
}
public Double GetMedian(){
    if( N % 2 == 0 ) return(left.peek()+ right.peek())/2.0;
    else return(double) right.peek();
}

PriorityQueue介绍

PriorityQueue（优先队列）是一种特殊的队列，它可以保证每次取出的堆顶元素都是最小值（或者最大值）。其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。

特点：

  • PriorityQueue是一个无限制的队列，并且动态增长。
  • 它不允许null对象。
  • 添加到PriorityQueue的对象必须具有可比性。
  • *默认情况下，优先级队列的对象按自然顺序排序。
  • 比较器可用于队列中对象的自定义排序。
  • 优先级队列的头部是基于自然排序或基于比较器的排序的最小元素。当我们轮询队列时，它从队列中返回头对象。
  • 如果存在多个具有相同优先级的对象，则它可以随机轮询其中任何一个。
  • PriorityQueue 不是线程安全的。PriorityBlockingQueue在并发环境中使用。
  • 它为add和poll方法提供了**O（log（n））**时间。

方法：

  • add()和offer()

add(E e)和offer(E e)的语义相同，都是向优先队列中插入元素，只是Queue接口规定二者对插入失败时的处理不同，前者在插入失败时抛出异常，后则则会返回false。对于PriorityQueue这两个方法其实没什么差别。

img

  • element()和peek()

element()和peek()的语义完全相同，都是获取但不删除队首元素，也就是队列中权值最小的那个元素，二者唯一的区别是当方法失败时前者抛出异常，后者返回null。根据小顶堆的性质，堆顶那个元素就是全局最小的那个；由于堆用数组表示，根据下标关系，0下标处的那个元素既是堆顶元素。所以直接返回数组0下标处的那个元素即可。

img

  • remove()和poll()

remove()和poll()方法的语义也完全相同，都是获取并删除队首元素，区别是当方法失败时前者抛出异常，后者返回null。由于删除操作会改变队列的结构，为维护小顶堆的性质，需要进行必要的调整。

img

  • remove(Object object)

remove(Object o)方法用于删除队列中跟o相等的某一个元素（如果有多个相等，只删除一个），该方法不是Queue接口内的方法，而是Collection接口的方法。由于删除操作会改变队列结构，所以要进行调整；又由于删除元素的位置可能是任意的，所以调整过程比其它函数稍加繁琐。具体来说，remove(Object o)可以分为2种情况：1. 删除的是最后一个元素。直接删除即可，不需要调整。2. 删除的不是最后一个元素，从删除点开始以最后一个元素为参照调用一次siftDown()即可。此处不再赘述。

img

代码实现

参考文献：

[41.1 数据流中的中位数 | CS-Notes (cyc2018.xyz)](http://www.cyc2018.xyz/算法/剑指 Offer 题解/41.1 数据流中的中位数.html)

JCFInternals/8-PriorityQueue.md at master · CarpenterLee/JCFInternals (github.com)