Java数据结构 - 优先级队列（PriorityQueue）_java 优先级队列

一、概念定义

我们已经知道队列是一种先进先出（FIFO）的数据结构，但是有些情况下，队列不能满足我们的一些需求，我们需要根据元素的优先级来进行操作，优先级高的元素先出队列。

例如：

• 医院的夜间门诊系统

  队列元素是病人对象

  优先级是病人的病情严重情况、挂号时间

• 电商网站的特卖、抢购系统

  当用户提交订单请求时，可以将普通用户和VIP用户的订单都放入队列里，普通用户的优先级别最低，VIP用户根据其会员等级来决定优先级，即使普通用户和VIP用户同时下单，级别高的用户可以先抢购到商品。如果在全都是普通用户的情况下，则根据用户的下单时间来出队。

在上面这些场景下，后台操作的数据具有优先级，那么普通的队列就在这里不适合，所以我们需要用到优先级队列PriorityQue。

优先级队列应该提供两个最基本的操作：一是返回最高优先级对象；二是添加新的对象。

二、优先级队列的结构

2.1 堆的概念定义

JDK1.8中的PriorityQueue底层使用了堆的数据结构，那么我们先了解一下堆的概念。

堆通常是一个可以被看做一棵二叉树的数组对象。堆总是满足下列性质：

• 堆中某个结点的值总是不大于或不小于其父结点的值；
• 堆总是一颗完全二叉树。

将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆是非线性数据结构，相当于一维数组，有两个直接后继。

堆的定义如下：n个元素的序列{k1, k2, k3, …, kn}当且仅当满足下关系时，称之为堆。

若将和此序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1, k2, k3, …, kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。

2.2 堆的存储方式

从堆的概念知道，堆是一棵完全二叉树，以层序的规则采用顺序的方式来高效存储。

大根堆示意图：

如果是非完全二叉树，则不适合使用顺序方式来存储，因为为了能够还原二叉树，数组空间里必须要存储空结点，就会导致空间利用率比较低。

如下图的非完全二叉树：

将元素存储到数组中后，可以根据二叉树的性质5对树进行还原。假设i为节点在数组中的下标，则有：

• 如果i为0，则i表示的节点为根结点，否则i结点的双亲结点为(i-1)/2。
• 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子。
• 如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

2.3 堆的创建

2.3.1 堆向下调整

给定一个序列{ 27,15,19,18,28,34,65,49,25,37 }，如何将构建成堆？

首先我们将其展现为完全二叉树的形式：

仔细观察上图可以发现，除根节点外，其左右子树已经满足堆的性质，即为小根堆，所以我们通过从根节点开始向下调整，可以将它构建成堆。

向下调整算法过程：

通过一对指针（父节点指针，下文用parent代指 和 孩子节点指针，下文用child代指）来进行调整。

1. 首先将parent指向下标0的位置，通过parent来求child的位置 (parent-1)/2 （注意：如果父节点有孩子，则一定是先有左孩子），再判断是否有右孩子，然后根据左孩子节点+1得出右孩子节点）。
2. 比较出左右孩子节点的较小值并使child指向它，再将parent与child比较，如果parent大于child的话就进行交换。
3. 交换之后parent大的节点值向下移动可能导致子树不满足堆的性质，需要修改parent和child的指向来继续向下调整，将parent = child, child = parent * 2 + 1 然后重复2操作。
4. 如果parent的左孩子不存在了，则parent为叶子节点了，调整结束。

调整图解过程：

实现代码：

private void shiftDown(int parent,int len){
    int child = parent * 2 + 1; //左孩子结点
    while(child < len){ //如果孩子结点索引等于或大于len,则不存在该孩子结点，其双亲结点为叶子结点
        //比较左右孩子结点值的大小
        if(child + 1 < len && elem[child] < elem[child+1]){ //(child+1 < len)判断是否有右孩子
            child++; //child结点一定记录值大的那个
        }
        //这里创建大根堆，比较孩子结点是否大于双亲结点
        if(elem[child] > elem[parent]){ //大于就交换
            int temp = elem[child];
            elem[child] = elem[parent];
            elem[parent] = temp;
            //因为被调整的孩子结点可能也是其他孩子的双亲结点，所以继续向下调整
            parent = child;
            child = parent * 2 + 1;
        }else{
            break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.3.2 堆的创建

如果想把序列{ 27,15,19,18,28,34,65,49,25,37 } 调整为大根堆，此时根节点的左右子树不满足堆的性质，我们不能在这里通过向下调整来完成，相反，我们要使用向上调整。

调整图解过程：

实现代码：

//调整堆（将初始堆调整为大根堆或小根堆）
public void createHeep(){
    //从最后一个结点的双亲结点开始调整
    int len = elem.length;
    for(int i = (len - 1 - 1) / 2; i >= 0; i--){
        shiftDown(i,len);
    }
}

private void shiftDown(int parent,int len){
    int child = parent * 2 + 1; //左孩子结点
    while(child < len){ //如果孩子结点索引等于或大于len,则不存在该孩子结点，其双亲结点为叶子结点
        //比较左右孩子结点值的大小
        if(child + 1 < len && elem[child] < elem[child+1]){ //(child+1 < len)判断是否有右孩子
            child++; //child结点一定记录值大的那个
        }
        //这里创建大根堆，比较孩子结点是否大于双亲结点
        if(elem[child] > elem[parent]){ //大于就交换
            int temp = elem[child];
            elem[child] = elem[parent];
            elem[parent] = temp;
            //因为被调整的孩子结点可能也是其他孩子的双亲结点，所以继续向下调整
            parent = child;
            child = parent * 2 + 1;
        }else{
            break;
        }
    }
}
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

2.3.3 构建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明 (时间复杂度本来看的就是 近似值，多几个节点不影响最终结果)

第1层，2^0个节点，需要向下移动h-1层。

第2层，2^1个节点，需要向下移动h-2层。

第3层，2^2个节点，需要向下移动h-3层。

第4层，2^3个节点，需要向下移动h-4层。

…

第h-1层，2^h-2个节点，需要向下移动1层。

推导公式这里直接给出课件里的哈哈！

因此：建堆的时间复杂度为O(N)。

2.4 堆的插入与删除

2.4.1 堆底插入元素

在堆中插入新元素主要分为两个操作：

1. 检查数组容量是否足够，不够则扩容，将新元素插入到数组末尾位置，堆元素个数+1。
2. 从插入结点开始向上调整，直到满足堆的结构性质。

向上调整算法过程（以大根堆为例）：

1. 同向下调整一样使用双指针parent和child,先使child指向新插入结点位置，然后将parent指向 (child-1)/2 父结点位置。
2. 比较parent和child的值，如果parent小则交换值，否则直接结束（因为当parent值不小于child值时，已经满足了堆结构性质）。
3. 交换之后大的值向上移动可能破坏上层堆的结构，所以需要让child指向parent，parent再重新指向 (child-1)/2 父结点位置，然后重复步骤2。
4. 如果child指向了0下标的位置，则调整结束。

插入元素图解过程：

2.4.2 堆顶删除元素

首先要知道我们这里操作的是优先级队列，而队列必须满足尾进头出原则，堆顶元素只可能是堆中优先级最高的，先访问的一定是堆顶的元素。

删除堆顶元素也是需要两个操作

1. 将堆顶元素与堆尾元素进行交换，堆元素个数-1。
2. 从堆顶结点开始向下调整结构。

向下调整算法过程（以大根堆为例）：

这里的调整算法与上文 堆的创建 中堆向下调整逻辑一致，只是比较规则不同（这里是大根堆，所以当parent值小于child值时进行交换），调整的图解过程也一致，所以不再赘述。

三、模拟实现优先级队列容器类

/**
 * 模拟实现PriorityQueue优先级队列容器类
 * @param <E>
 */
public class MyPriorityQueue2<E extends Comparable<E>> {

    //存放堆元素
    private Object[] elemData;
    //默认初始容量
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    //堆元素个数
    private int size;
    //对象比较器
    Comparator<E> comparator;

    /**
     * 创建默认容量大小的队列对象，并使用元素的自然排序规则
     */
    public MyPriorityQueue2(){
        this(DEFAULT_INITIAL_CAPACITY,null);
    }

    /**
     * 创建指定容量大小的队列对象，并使用元素的自然排序规则
     * @param initialCapacity 指定初始容量
     */
    public MyPriorityQueue2(int initialCapacity){
        this(initialCapacity,null);
    }

    /**
     * 创建默认初始容量大小的队列对象，并使用指定比较器对象
     * @param comparator 指定比较器
     */
    public MyPriorityQueue2(Comparator<E> comparator){
        this(DEFAULT_INITIAL_CAPACITY,comparator);
    }

    /**
     * 创建指定初始容量大小的队列对象并初始化比较器对象成员
     * @param initialCapacity 指定初始容量
     * @param comparator 比较器对象
     */
    public MyPriorityQueue2(int initialCapacity, Comparator<E> comparator){
        this.elemData = new Object[initialCapacity];
        this.comparator = comparator;
    }

    /**
     * 将指定元素入队列，然后根据比较规则来调整堆结构
     * @param e 指定元素对象
     * @return true
     */
    public boolean offer(E e){
        isFull();

        int i = size++;
        elemData[i] = e;
        if(i == 0){ //首次入队
            return true;
        }
        if(comparator == null){
            shiftUpWithNaturalSorting(i,size);
        }else{
            shiftUpWithComparatorSorting(i,size);
        }
        return true;
    }

    //使用自然排序比较规则来向上调整
    @SuppressWarnings("unchecked")
    private void shiftUpWithNaturalSorting(int child,int len){
        int parent = (child - 1) / 2;
        while (child > 0){
            Comparable<E> parentElem = (Comparable<E>) elemData[parent];
            if(parentElem.compareTo((E)elemData[child]) > 0){
                E temp = (E)elemData[parent];
                elemData[parent] = elemData[child];
                elemData[child] = temp;
                child = parent;
                parent = (child - 1) / 2;
            }else{
                break;
            }
        }
    }

    //使用定制排序比较规则来向上调整
    @SuppressWarnings("unchecked")
    private void shiftUpWithComparatorSorting(int child,int len){
        int parent = (child - 1) / 2;
        while (child > 0){
            if(comparator.compare((E)elemData[parent],(E)elemData[child]) > 0){
                E temp = (E)elemData[parent];
                elemData[parent] = elemData[child];
                elemData[child] = temp;
                child = parent;
                parent = (child - 1) / 2;
            }else{
                break;
            }
        }
    }

    /**
     * 将队列中优先级最高的元素出队
     * @return
     */
    public E poll(){
        if(isEmpty()){
            return null;
        }

        E polled = (E)elemData[0];
        elemData[0] = elemData[--size];

        if(comparator == null){
            shiftDownComparable();
        }else{
            shiftDownComparator();
        }
        return polled;
    }

    @SuppressWarnings("unchecked")
    private void shiftDownComparable(){
        int parent = 0;
        Comparable<E> parentEle = (Comparable<E>) elemData[parent];
        int child = 1;
        while (child < size){
            if(child + 1 < size && ((Comparable<E>)elemData[child]).compareTo((E)(elemData[child+1])) > 0){
                child++;
            }
            if(parentEle.compareTo((E)elemData[child]) > 0){
                Object temp = elemData[parent];
                elemData[parent] = elemData[child];
                elemData[child] = temp;
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }

    @SuppressWarnings("unchecked")
    private void shiftDownComparator(){
        int parent = 0;
        int child = 1;
        while (child < size){
            if(comparator.compare((E)elemData[child],(E)elemData[child+1]) > 0){
                child++;
            }
            if(comparator.compare((E)elemData[parent],(E)elemData[child]) > 0){
                Object temp = elemData[parent];
                elemData[parent] = elemData[child];
                elemData[child] = temp;
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }

    //检查队列空间是否足够，不够就扩容
    private void isFull(){
        int len = elemData.length;
        if(size == len){
            elemData = Arrays.copyOf(elemData, len * 2);
        }
    }

    /**
     * @return 返回当前堆顶元素，如果堆为空则返回null
     */
    @SuppressWarnings("unchecked")
    public E peek(){
        if (isEmpty()){
            return null;
        }else{
            return (E)elemData[0];
        }
    }

    /**
     * @return 队列是否为空
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * @return 返回队列元素个数
     */
    public int size(){
        return size;
    }

}
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200

四、Java集合框架中的PriorityQueue

通过类继承图看到PriorityQueue是实现了Queue接口的，所以也实现了队列的基本方法。

在类结构当中有几种重载的构造方法，可以根据不同的形参列表来实例化不同属性的对象。

类当中还有许多基本的方法，这里我们主要关注以下三个。

1. offer(E)

2.poll()

3.peek()

五、优先级队列的应用

示意性的模拟一个优先级队列使用场景，这里拿上文中的电商网站的特卖、抢购系统来作例子。

import java.util.Comparator;
import java.util.PriorityQueue;

public class PriorityQueueTest {

    //优先级队列的应用
    public static void main(String[] args) {
        //准备一批用户对象
        User u1 = new User(1001, "张三", MembershipLevel.V8);
        User u2 = new User(1002, "李四", MembershipLevel.V5);
        User u3 = new User(1003, "王五", MembershipLevel.V5);
        User u4 = new User(1004, "赵六", MembershipLevel.V3);
        User u5 = new User(1005, "孙七", MembershipLevel.V1);
        User u6 = new User(1006, "周八", MembershipLevel.V0);

        //假设某商品抢购场景，让所有用户都入队列，然后根据用户会员等级出队，先出队的就可以先抢到
        PriorityQueue<User> userPriorityQueue = new PriorityQueue<>(new LevelComparator());
        userPriorityQueue.offer(u6);
        userPriorityQueue.offer(u5);
        userPriorityQueue.offer(u4);
        userPriorityQueue.offer(u3);
        userPriorityQueue.offer(u2);
        userPriorityQueue.offer(u1);

        int userNumber = userPriorityQueue.size();
        for(int i = 0; i < userNumber; i++){
            User user = userPriorityQueue.poll();
            if (user != null) {
                System.out.println(user.getName() + "是第" + (i+1) + "个抢到商品的。");
            }
        }

    }
}

//用户会员等级
enum MembershipLevel{
    V0,V1,V2,V3,V4,V5,V6,V7,V8;
}

//用户类
class User{
    private int id;
    private String name;
    private MembershipLevel level;

    public User(int id, String name, MembershipLevel level) {
        this.id = id;
        this.name = name;
        this.level = level;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public MembershipLevel getLevel() {
        return level;
    }

    public void setLevel(MembershipLevel level) {
        this.level = level;
    }
}

//根据用户会员等级来比较
class LevelComparator implements Comparator<User> {
    @Override
    public int compare(User o1, User o2) {
        return o2.getLevel().compareTo(o1.getLevel());
    }
}
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

这个例子还是比较现实的哈哈。

六、经典面试题Top-K问题

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都 不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆

• 前k个最大的元素，则建小堆
• 前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

面试题 17.14. 最小K个数

具体的题目讲解就不放在本文讲解了，之后更新到面试题栏目中。