0%

Java 堆与优先级队列(三):堆和 PriorityQueue 的应用

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
    37
    public 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 个最大的元素。
  • Demo:

    1
    2
    3
    4
    5
    6
    TopK<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
    47
    public 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
    6
    Median<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
-------------------- 本文结束感谢您的阅读 --------------------