优先队列和堆

Posted on | In

优先队列

wikipedia

优先队列是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用堆来实现。

普通队列：先进先出；后进后出

优先队列：出队顺序和入队顺序无关；和优先级相关

使用场景

  1. 即时战略游戏，自动打怪，怪也是源源不断的增加
  2. 医生治疗优先级病人，动态的，病人会远远不断的增加

优先级强调的是动态的过程，数据是不断新增的

实现

初级实现

有许多简单低效的实现。如用一个有序的数组；或使用无序数组，在每次取出时搜索全集合，这种方法插入的效率为O(1)，但取出时效率为O(n)。

典型实现

出于性能考虑，优先队列用堆)来实现，具有O(log n)时间复杂度的插入元素性能，O(n)的初始化构造的时间复杂度。如果使用自平衡二叉查找树，插入与删除的时间复杂度为O(log n)，构造二叉树的时间复杂度为O(n log n)。

从计算复杂度的角度，优先级队列等价于排序算法。

有一些特殊的堆)为优先队列的实现提供了额外的性能：二叉堆的插入与提取操作的时间复杂度为O(log n)，并可以常量时间复杂度的peek操作。二项堆提供了几种额外操作。斐波那契堆的插入、提取、修改元素优先级等操作具有分摊常量时间复杂度，[1]，但删除操作的时间复杂度为O(log n)。Brodal queue具有最糟糕情况下的常量复杂度但算法相当复杂因而不具有实用性。

对于整型、浮点型等具有有限值域的元素的数据类型，优先队列有更快的实现。

入队 出队(拿出最大元素)
普通线性结构 $O(1)$ $O(n)$
顺序线性结构 $O(n)$ $O(1)$
堆 $O(logn)$ $O(logn)$

堆

wikipedia

堆（英语：Heap）是计算机科学中的一种特别的树状数据结构。若是满足以下特性，即可称为堆：“给定堆中任意节点P和C，若P是C的母节点，那么P的值会小于等于（或大于等于）C的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。

堆始于J. W. J. Williams在1964年发表的堆排序（heap sort），当时他提出了二叉堆树作为此算法的数据结构。堆在戴克斯特拉算法（英语：Dijkstra’s algorithm）中亦为重要的关键。

在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。[1]

二叉堆的特性

二叉堆是一颗完全二叉树

二叉堆的性质(Binary Heap)

  • 堆中某个节点的值总是不大于其父节点的值
  • 最大堆(相应的可以定义做小堆)
存储二叉树的方式

二叉树 顺序存储表示的话，可以用数组或链接串列来存储，由于是满二叉树就能紧凑排列而不浪费空间

1
2
3
4
5
6
7
8
9
10
11
如果1标记为根节点

parent(i) = i/2
left child (i) = 2*i
right child (i) = 2*i + 1
  
由于数组从0开始计算

parent(i) = (i-1)/2
left child (i) = 2*i + 1
right child (i) = 2*i + 2
支持的基本操作
  • 创建空堆
  • 向堆中添加元素和 Sift up
  • 向堆中取出最大元素和 Sift down
  • heapify 和 replace

add 和 extractMax 时间复杂度都是 $O(logn)$

replace：取出最大元素后，放入一个新元素

实现：可以先 extractMax，再 add，再次 $O(logn)$ 的操作

实现：可以直接将堆顶元素替换以后 Sift Down，一次 $O(logn)$ 的操作

heapify：将任意数组整理成堆的形状

Heapify 的算法复杂度

将 n 个元素逐个插入到一个空堆中，算法复杂度是 $0(nlogn)$

heapify 的过程，算法复杂度为 $0(n)$

MaxHeap 的具体实现
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;

    public MaxHeap(int capacity) {
        data = new Array<>(capacity);
    }

    public MaxHeap() {
        data = new Array<>();
    }

    public MaxHeap(E[] arr) {
        data = new Array<>(arr);
        for (int i = parent(data.getSize() - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    // 返回堆中的元素个数
    public int size() {
        return data.getSize();
    }

    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty() {
        return data.isEmpty();
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
    private int parent(int index) {
        if (index == 0)
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index - 1) / 2;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index) {
        return index * 2 + 1;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index) {
        return index * 2 + 2;
    }

    // 向堆中添加元素
    public void add(E e) {
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    // 添加一个元素 == 上浮
    private void siftUp(int k) {

        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
            data.swap(k, parent(k));
            k = parent(k);
        }
    }

    // 看堆中的最大元素
    public E findMax() {
        if (data.getSize() == 0)
            throw new IllegalArgumentException("Can not findMax when heap is empty.");
        return data.get(0);
    }

    // 取出堆中最大元素
    public E extractMax() {

        E ret = findMax();

        data.swap(0, data.getSize() - 1);
        data.removeLast();
        siftDown(0);

        return ret;
    }

    // 下沉
    private void siftDown(int k) {

        while (leftChild(k) < data.getSize()) {
            int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置
            if (j + 1 < data.getSize() &&
                    data.get(j + 1).compareTo(data.get(j)) > 0)
                j++;
            // data[j] 是 leftChild 和 rightChild 中的最大值

            if (data.get(k).compareTo(data.get(j)) >= 0)
                break;

            data.swap(k, j);
            k = j;
        }
    }

    // 取出堆中的最大元素，并且替换成元素e
    public E replace(E e) {

        E ret = findMax();
        data.set(0, e);
        siftDown(0);
        return ret;
    }
}
PriorityQueue 的具体实现
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
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

    private MaxHeap<E> maxHeap;

    public PriorityQueue() {
        maxHeap = new MaxHeap<E>();
    }

    @Override
    public void enQueue(E e) {
        maxHeap.add(e);
    }

    @Override
    public E deQueue() {
        return maxHeap.extractMax();
    }

    @Override
    public E getFront() {
        return maxHeap.findMax();
    }

    @Override
    public int getSize() {
        return maxHeap.size();
    }

    @Override
    public boolean isEmpty() {
        return maxHeap.isEmpty();
    }
}

案例

案例1：在 1 000 000 个元素中选出前 100 名

在 N 个元素中选出前 M 个元素

排序（归并排序，快速排序）？$NlogN$，

优先队列？$NlogM$

使用优先队列，维护当前看到的前 M 个元素

需要使用最小堆

1
1. 直接创建 1_000_000 个元素的数组 heapify「堆化」，然后通过 PriorityQueue.deQueue() 前 100 个元素
案例2：347. 前 K 个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]
说明：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

1
2
3
4
5
1. 最终返回的是具体的元素，元素的优先级是通过出现频率来判定的
2. 可以通过映射 TreeMap<Integer, Integer>来存储具体的「元素」和「频次」，直接通过非静态成员内部类封装 Frep int e,frep，Frep 类实现 Comparable 接口，重写 compareTo(Freq freq), 频次小的返回 1，从而让其成为最小堆，因为上面是通过 maxHeap 方式实现的，需要反过来。
3. 如果是通过 java.utils.java.util.PriorityQueue 方式类代替的话，则不需要反过来，因为 Java 默认实现是最小堆
4. java.utils.java.util.PriorityQueue 提供 public PriorityQueue(Comparator<? super E> comparator)，所以针对部分不能重写 compareTo 的类型，String 可以定制化比较逻辑，因为 String 默认逻辑是根据字符编码序号比较的，并且是不能覆盖 String 本身的逻辑
5. 当然也可以直接 new Comparator 匿名内部类的形式去处理比较逻辑，这种写的好处是可以在匿名内部类中直接操作外部变量（局部变量，成员变量），从而不需要使用 Frep 非静态成员内部类，直接通过 PriorityQueue 存储元素的值，然后具体的逻辑比较，通过匿名内部类访问局部变量 treeMap.get(e) 去获取频次比较，从而简化了代码，不需要非静态成员类去封装 e, freq
Solution1（非静态成员类封装 e, freq）
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
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;

public class Solution {


    class Freq implements Comparable<Freq> {

        int e, freq;

        public Freq(int e, int freq) {
            this.e = e;
            this.freq = freq;
        }

        @Override
        public int compareTo(Freq anther) {

            if (this.freq < anther.freq)
                return 1;
            else if (this.freq > anther.freq)
                return -1;
            else
                return 0;
        }

    }

    public List<Integer> topKFrequent(int[] nums, int k) {

        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }

        PriorityQueue<Freq> pq = new PriorityQueue<>();
        map.keySet().forEach(key -> {

            if (pq.getSize() < k) {
                pq.enQueue(new Freq(key, map.get(key)));
            } else if (map.get(key) > pq.getFront().freq) {
                pq.deQueue();
                pq.enQueue(new Freq(key, map.get(key)));
            }

        });

        LinkedList<Integer> list = new LinkedList<>();
        while (pq.getSize() > 0)
            list.add(pq.deQueue().e);
        return list;
    }

}
Solution2（PriorityQueue -》java.utils.java.util.PriorityQueue）
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
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.*;
import java.util.PriorityQueue;


public class Solution2 {

    class Freq implements Comparable<Freq> {

        int e, freq;

        public Freq(int e, int freq) {
            this.e = e;
            this.freq = freq;
        }

        @Override
        public int compareTo(Freq anther) {

            if (this.freq > anther.freq)
                return 1;
            else if (this.freq < anther.freq)
                return -1;
            else
                return 0;
        }

    }

    public List<Integer> topKFrequent(int[] nums, int k) {

        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }

        // 比较器代替实现comparable接口
        PriorityQueue<Freq> pq = new PriorityQueue<>();
        map.keySet().forEach(key -> {

            if (pq.size() < k) {
                pq.add(new Freq(key, map.get(key)));
            } else if (map.get(key) > pq.peek().freq) {
                pq.remove();
                pq.add(new Freq(key, map.get(key)));
            }

        });

        LinkedList<Integer> list = new LinkedList<>();
        while (pq.size() > 0)
            list.add(pq.remove().e);
        return list;
    }

}
Solution3（Comparator 形式代替 Comparable）
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
import java.util.*;
import java.util.PriorityQueue;


public class Solution2 {

    class FreqComparator implements Comparator<Freq> {

        @Override
        public int compare(Freq o1, Freq o2) {
            return o1.freq - o2.freq;
        }
    }

    public List<Integer> topKFrequent(int[] nums, int k) {

        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }

        // 比较器代替实现comparable接口
        PriorityQueue<Freq> pq = new PriorityQueue<>(new FreqComparator());
        map.keySet().forEach(key -> {

            if (pq.size() < k) {
                pq.add(new Freq(key, map.get(key)));
            } else if (map.get(key) > pq.peek().freq) {
                pq.remove();
                pq.add(new Freq(key, map.get(key)));
            }

        });

        LinkedList<Integer> list = new LinkedList<>();
        while (pq.size() > 0)
            list.add(pq.remove().e);
        return list;
    }

}
Solution4（Comparator 匿名类代替非静态成员类）
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
import java.util.PriorityQueue;
import java.util.*;

public class Solution3 {


    public List<Integer> topKFrequent(int[] nums, int k) {

        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }

        // 匿名类==>非静态成员类
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });
        map.keySet().forEach(key -> {

            if (pq.size() < k) {
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }

        });

        LinkedList<Integer> list = new LinkedList<>();
        while (pq.size() > 0)
            list.add(pq.remove());
        return list;
    }

}
Solution5（lambda 简化代码）
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
import java.util.PriorityQueue;
import java.util.*;

public class Solution4 {

    public List<Integer> topKFrequent(int[] nums, int k) {

        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }

        // lambda 表达式
        PriorityQueue<Integer> pq = new PriorityQueue<>(
                (a, b) -> map.get(a) - map.get(b));
        map.keySet().forEach(key -> {

            if (pq.size() < k) {
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        });

        LinkedList<Integer> list = new LinkedList<>();
        while (pq.size() > 0)
            list.add(pq.remove());
        return list;
    }

}