1. PriorityQueue 除了用作优先级队列，还有哪些应用
- 求前 K 个最大的元素：元素个数不确定，数据量可能很大，甚至源源不断到来，但需要知道到目前为止的最大的前 K 个元素这个问题的变体有：求前 K 个最小的元素、求第 K 个最大的元素、求第 K 个最小元素
- 求中值元素：中值不是平均值，而是排序后中间那个元素的值，同样，数据量可能很大，甚至源源不断到来
2. 如果所有元素都已知，那么求前 K 个最大元素的思路是
- 排序。排序后取最大的 K 个就可以了，排序可以使用
Arrays.sort()方法，效率为O(N * log2(N))。不过，如果 K 很小，比如是 1，就是取最大值，对所有元素完全排序是毫无必要的 - 选择。循环选择 K 次，每次从剩下的元素中选择最大值，这个效率是
O(N * K)，如果 K 的值大于 log2(N)，这个就不如完全排序了
3. 如果所有元素动态添加，那么求前 K 个最大元素的思路是
- 思路：维护一个长度为 K 的数组。最前面的 K 个元素就是目前最大的 K 个元素，以后每来一个新元素的时候，都先找数组中的最小值，将新元素与最小值相比。如果小于最小值，则什么都不用变，如果大于最小值，则将最小值替换为新元素（类似于生活中的末尾淘汰）
- 这样，数组中维护的永远是最大的 K 个元素，而且不管源数据有多少，需要的内存开销是固定的，就是长度为 K 的数组。不过，每来一个元素，都需要找最小值，都需要进行 K 此比较，能不能减少比较次数呢
- 能。解决方法是使用最小堆维护这 K 个元素。最小堆中，根即第一个元素永远都是最小的，新来的元素与根比就可以了。如果小于根，则堆不需要变化，否则用新元素替换根，然后向下调整堆即可，调整的效率为
O(log2(K))。这样，总体的效率就是O(N * log2(K))，这个效率非常高，而且存储成本也很低
4. 求前 K 个最大的元素：TopK
代码：
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
37public class TopK<E> {
private PriorityQueue<E> p;
private int k;
public TopK(int k) {
this.k = k;
this.p = new PriorityQueue<> (k);
}
public void addAll(Collection<? extends E> c) {
for(E e : c) {
add(e);
}
}
public void add(E e) {
if(p.size() < k) {
p.add(e);
return;
}
Comparable<? super E> head = (Comparable<? super E>) p.peek();
if(head.compareTo(e) > 0) { //小于 TopK 中的最小值，不用变
return;
}
//新元素替换掉原来的最小值成为 TopK 之一
p.poll();
p.add(e);
}
public <T> T[] toArray(T[] a) {
return p.toArray(a);
}
public E getKth() {
return p.peek();
}
}分析
- TopK 内部使用一个优先级队列和
k，构造方法接收一个参数k，使用PriorityQueue的默认构造方法，假定元素实现了Comparable接口 add()方法实现向其中动态添加元素，如果元素个数小于k直接添加，否则与最小值比较，只在大于最小值的情况下添加，添加前，先删掉原来的最小值。addAll()方法循环调用add()方法toArray()方法返回当前的最大的 K 个元素，getKth()方法返回第 K 个最大的元素
- TopK 内部使用一个优先级队列和
Demo
1
2
3
4
5
6TopK<Integer> top5 = new TopK<> (5);
top5.addAll(Arrays.asList(new Integer[] {100, 1, 2, 5, 6, 7, 34, 9, 3, 4, 5, 8, 23, 21, 90, 1, 0}));
System.out.println(Arrays.toString(top5.toArray(new Integer[0])));
System.out.println(top5.getKth());
//输出：[21, 23, 34, 100, 90] 和 21
5. 中值的概念是
- 中值就是排序后中间那个元素的值
- 如果元素个数为奇数，中值是没有歧义的
- 如果元素个数为偶数，中值可能有不同的定义。可以为偏小的那个，也可以是偏大的那个，或者两者的平均值，或者任意一个
6. 如果所有元素都已知，怎样求中值
- 排序，排序后取中间那个值就可以了
- 排序可以使用
Arrays.sort()方法，效率为O(N * log2(N))
7. 如果所有元素动态添加，怎样求中值
思路
- 可以使用两个堆，一个最大堆，一个最小堆
步骤：
- 假设当前的中位数是 m，最大堆维护的是 <=m 的元素，最小堆维护的是 >=m 的元素，但两个堆都不包含 m
- 当新的元素到达时，比如 e，将 e 与 m 进行比较，若 e<m，则将其加入最大堆中，否则将其加入最小堆中
- 第 2 步后，如果此时最小堆和最大堆的元素个数的差值 >=2，则将 m 加入元素个数少的堆中，然后从元素个数多的堆将根节点移除并赋值给 m
8. 求中值：Median
代码
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
47public class Median<E> {
private PriorityQueue<E> minP; //最小堆
private PriorityQueue<E> maxP; //最大堆
private E m; //当前中值
public Median() {
this.minP = new PriorityQueue<> ();
this.maxP = new PriorityQueue<> (11, Collections.reverseOrder());
}
private int compare(E e, E m) {
Comparable<? super E> cmpr = (Comparable<? super E>) e;
return cmpr.compareTo(m);
}
public void add(E e) {
if(m == null) { //第一个元素
m = e;
return;
}
if(compare(e, m) <= 0) {
//小于中值，加入最大堆
maxP.add(e);
} else {
minP.add(e); //加入最小堆
}
if(minP.size() - maxP.size() >= 2) {
//最小堆元素个数多，即大于中值的数多
//将 m 加入到最大堆中，然后将最小堆中的根移除赋给 m
maxP.add(this.m);
this.m = minP.poll();
} else if(maxP.size() - minP.size() >= 2) {
minP.add(this.m);
this.m = maxP.poll();
}
}
public void addAll(Collection<? extends E> c) {
for(E e : c) {
add(e);
}
}
public E getM() {
return m;
}
}Demo
1
2
3
4
5
6Median<Integer> median = new Median<> ();
List<Integer> list = Arrays.asList(new Integer[] {34, 90, 67, 1, 4, 5, 6, 7, 9, 10});
median.addAll(list);
System.out.println(median.getM());
//输出中值 9