当前位置:   article > 正文

Java数据结构 - 优先级队列(PriorityQueue)_java 优先级队列

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个最小的元素,则建大堆
  1. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素

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

面试题 17.14. 最小K个数

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/791693
推荐阅读
相关标签
  

闽ICP备14008679号