算法 堆排序 & PriorityQueue

words: 1.5k    views:    time: 6min
算法设计
PriorityQueue

在有些场景中，并不一定要求所有元素有序，而只需知道其中最大或最小的 K 个元素，比如在优先级队列中，只要每次都能获取到队列中最大或最小的的元素即可，于是有人想到了利用树的形式来组织数据，这里称为堆。

1. 二叉堆

二叉堆定义：当一颗二叉树中的每个节点都不小于它的子节点时，就称其为堆有序；

比如对于给定的数组：[5,2,10,7,6,3,8,4]，可以将其表示成二叉堆，可以看出来，其必然是一颗完全二叉树：

这样如果将数组中元素的位置与堆中的节点对应，那么对于任意位置 k 的元素，则有：
父结点位置为：(k-1)/2
左子节点位置为：2k + 1
右子节点位置为：2k + 2

但我们目标是希望将其转化为有序堆，当然根据比较关系还可以分为大根堆或者小根堆

1.1. 插入

类似于二叉查找树，可以先插入到末尾树叶的位置，然后再由树叶向上进行比较交换，即上浮操作

这样如果插入的末尾位置是 k，那么我们可以如下对其进行调整

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/algorithms/TopHeap.java
1
2
3
4
5
6
private void up(int k){
    while(k > 0 && comp(array, (k-1)/2, k, comp) < 0){
        swap(array, (k-1)/2, k);
        k = (k-1)/2;
    }
}

1.2. 删除

同样类似于二叉查找树，可以先将对顶与树叶对换，将删除操作转化为对树叶的删除，然后再由堆顶向下进行比较交换，即下沉操作

那么在对换删除之后，对堆顶的下沉操作可以表示如下

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/algorithms/TopHeap.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void down(int k, int len, Object[] array) { 
    int child; 
    while ((child = 2 * k + 1)  < len) {
        if (child + 1 < len && comp(array, child, child + 1, comp) < 0) {
            child++;    // 从左右子节点中选取一个较大值
        }
        if (comp(array, k, child, comp) > 0){ 
            break;      // 如果父结点已经不小于左右子节点，则直接结束
        }

        swap(array, k, child); // 父节点下沉，子节点上浮
        k = child;             // 继续向下比较  
    }
}

1.3. 转化

有时对于给定的数组，希望将其初始化为有序堆，那么思路就是从下到上，从右向左，对每个非叶子节点进行遍历，尝试进行下沉操作

1
2
3
for (int i = length / 2; i >= 0; i--) { 
    down(array, i, length);
}

1.4. 复杂度分析

对于 插入 和 删除，最坏的情况就是一直从树叶上浮到堆顶或者从堆顶下沉到树叶，而堆是一颗完全二叉树，所以复杂度都不会超过 $\log_{2} {n}$

对于转换操作，最差的情况就是从下到上每个非叶子都需要与两个字节点进行比较并一直下沉到树叶位置

这样假设节点数为 $n$ 的堆（完全二叉树）高度为 $h$，那么在第 $k$ 层，最多有 $2^{k-1}$ 个节点，每个节点最多向下移动 $h-k$ 次，而每次移动对应 $2$ 次比较操作，那么 $k$ 层节点累计所需的比较次数应该是：$S_k=\sum^{h-1}_{k=1}{2^{k-1} \times 2 \times (h-k)}=\sum^{h-1}_{k=1}{2^k \times (h-k)}$

于是表达式展开为： $\:\:\: S_k=2(h-1) + 2^2(h-2) + 2^3(h-3) + … + 2^{h-1} \times 1$

再将表达式乘2则有：$2S_k=\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\: 2^2(h-1) + 2^3(h-2) + … + 2^{h-1} \times 2 + 2^h \times 1$

令两式相减，得：$\:\:\:\:\:\:\:\: S_k=-2(h-1) + (2^2 + 2^3 + … + 2^{h-1}) + 2^h=-2(h-1) + 2^{h+1} - 4=2^{h+1}-2h-2$

而对于高度为 $h$ 的完全二叉树，其对应的节点数 $n$ ，满足关系：$2^{h-1} \leq n \leq 2^h-1$，即 $\log_{2} {(n+1)} \leq h \leq \log_{2} {n} + 1$

因此，$S_k=2^{h+1}-2h-2 = 4 \times 2^{h-1}-2h-2 \leq 4n - 2\log_{2} {(n+1)} - 2 \in O(n)$

2. 示例

借助上面的操作，下面用数组尝试实现一个容量固定的堆TopHeap，支持基本的put和take操作，并且如果put后超过了容量就自动弹出堆顶，这样再处理类似TopK的问题时会比较方便，比如如果希望想从大量输入中筛选出K个最大值，只需构造一个容量为K的小顶堆，这样当输入量超过K之后，每次put都会弹出当前最小值，而留下的就是K个最大值

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/algorithms/TopHeap.java
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
public class TopHeap<T extends Comparable<? super T>> {

    private final Comparator<? super T> comp; // 比较器

    private final Object[] array; // 元素数组

    private final int capacity; // 容量

    private int size; // 元素实际个数

    private int compTimes; // 记录比较次数

    public TopHeap(int capacity, Comparator<? super T> comp){
        this.comp = comp;
        this.capacity = capacity;
        this.array = new Object[capacity + 1]; 
    }
    
    // ... ...

    public T take(){
        if(size == 0){
            return null;
        }

        T t = (T)array[0];
        array[0] = array[size - 1];
        if(size > 2){
            down(0, size, array);
        }
        size--;
        return t;
    }

    public void put(T t){ 
        array[size] = t;
        if(size > 0){
            up(size);
        }
        if(++size > capacity){
            take();
        }
    }
    
    // ... ... 
}

3. 应用 PriorityQueue

堆排序在Java中最典型的应用便是优先级队列PriorityQueue，它也是基于数组实现的，基本的put和take操作与上面的思路是一样的，区别就是当put时如果检测到要超过数组容量，它会对数组进行扩容。至于具体的扩容规则类似于 ArrayList，即如果数组长度小于64，直接扩为2倍，否则扩容为1.5倍；

在PriorityQueue的基础上，java还提供了可阻塞、线程安全的PriorityBlockingQueue；以及DelayQueue，其获取操作在阻塞的基础上又增加了一个等待时间的限制；而定时任务执行器ScheduledThreadPoolExecutor内也是基于一个部DelayedWorkQueue实现的。


参考：

  1. 《算法》
  2. https://www.cnblogs.com/jingmoxukong/p/4303826.html
  3. https://zhuanlan.zhihu.com/p/341249538