35 通过可排序的优先队列解决紧急就医问题
Diego38 69 1

1. 前言

像Map、集合类这类数据结构都有支持可排序特性的类,而队列也不例外,队列不一定总是先进先出的,在一定场景允许用户传入可排序的元素,优先级高的元素先出队。

本节我们就介绍下支持排序的优先队列。

2. 优先队列的分类和使用场景

优先队列主要有两种,一种是线程不安全的PriorityQueue,内部是基于堆排序来实现的有序,另外一种就是基于PriorityQueue做了并发安全控制的阻塞优先队列PriorityBlockingQueue。

2.1 PriorityQueue的场景和实现

PriorityQueue是基于数组实现的,是有序排序的非线程安全版。

我们看一个例子:

public class PriorityQueueTest {

    public static void main(String[] args) {
        Queue<Integer> queue = new PriorityQueue<>(100);
        for (int i = 0; i < 50; i++) {
            queue.add(ThreadLocalRandom.current().nextInt(100));
        }
        for (int i = 0; i < 50; i++) {
            System.out.println("出队:" + queue.poll());
        }
    }

}

输出如下:

出队:3
出队:3
出队:4
..
出队:90
出队:91
出队:91
出队:94

发现是有序的。使用很简单,关键要了解内部实现,PriorityQueue实现了队列接口,必然有offer入队和poll出队两个方法, 基于数组实现,构造函数接收一个初始容量的设定,队列不停接收新的元素,使用堆排序最合适。

因此我们来看下PriorityQueue入队和出队做了哪些操作:

  • 入队offer(e)过程:如果越界—>扩容调用grow方法—>siftup(e)—>返回true
  • 出队poll():result=queue[0]—>siftdown(e)—返回第一个元素
  • 入队调用方法siftup会触发自底向上的堆排序
  • 出队需要调用方法siftdown触发自顶向下的堆排序
  • grow是通过数组拷贝进行扩容
  • siftdown是自顶向下堆排序,siftup是自底向上堆排序
  • PriorityQueue是采用的小顶堆,通过传递的comparator或者自身来排序。小的在上面,大的在子节点。每次入队保持有序,入队过程实际上变成将新元素插入到合适位置而已,无需每次触发全排序。而每次出队是继续保持小顶堆的过程。

小顶堆:每个结点的值都小于或等于其左右孩子结点的值

从以下图示可以看出siftdown和siftup的操作过程 image

  • siftDown对应于出队,实际上将排在首位的第一个元素从堆顶移除;依次经历3和4两个叶子节点比较,3往上移位,7和9比较,7往上移动。
  • siftUp对应于入队,实际上将新元素加入到小顶堆;从图中2元素依次经历了和左叶子节点6比较,在和4比较,最终成为左子树的根节点。

2.2 支持阻塞的PriorityBlockingQueue

是基于PriorityQueue实现,内部通过加锁Lock + Condition控制空时阻塞来实现的,同样在容量不足时会进行扩容,不过是在加锁条件下完成的。

我们看下offer的代码:

public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        final ReentrantLock lock = this.lock;
        //加锁
        lock.lock();
        int n, cap;
        Object[] array;
        while ((n = size) >= (cap = (array = queue).length))
            //尝试扩容
            tryGrow(array, cap);
        try {
            Comparator<? super E> cmp = comparator;
            if (cmp == null)
                //排序
                siftUpComparable(n, e, array);
            else
                //排序
                siftUpUsingComparator(n, e, array, cmp);
            size = n + 1;
            notEmpty.signal();
        } finally {
            //释放锁
            lock.unlock();
        }
        return true;
    }

用图形表示就是 image

阻塞实际只发生出队情况,因为出队时往往因为队列为空,造成线程等待。

3. 通过可排序的优先队列解决紧急就医问题

在医疗资源有限的情况下,急诊是可以插队的,可以优先就诊,这就需要优先队列来实现。代码如下:

package com.mooc.house;

import java.util.concurrent.PriorityBlockingQueue;
import java.util.concurrent.ThreadLocalRandom;

public class PriorityBlockingQueueTest {

    static class Patient  implements Comparable<Patient>{
        public String name;
        public Double damageScore;

        public Patient(String name, Double damageScore) {
            this.damageScore = damageScore;
            this.name = name;
        }

        @Override
        public int compareTo(Patient o) {
            return this.damageScore - o.damageScore > 0 ? -1  : 1 ;
        }
    }

    static PriorityBlockingQueue<Patient> queue = new PriorityBlockingQueue<>();

    public static void main(String[] args) {
        //多地出现普通病情
        for (int i = 0 ; i < 9 ; i++) {
            int finalI = i;
            new Thread(() -> {
                while (true) {
                    Patient patient = new Patient("普通病人", ThreadLocalRandom.current().nextDouble(100));
                    queue.offer(patient);
                }
            }).start();
        }

        //急诊病情集中发生
        new Thread(() -> {
            for (int i = 0; i < 1000 ; i++) {
                Patient patient = new Patient("急诊病人", 300D);
                queue.offer(patient);
            }
        }).start();


        //接诊任务开启,急诊优先
        new Thread(() -> {
            while (true) {
                Patient element = queue.poll();
                if (element != null) {
                    System.out.println("接诊到"  + element.name + " " + element .damageScore);
                }
            }
        }).start();
    }
}

输出结果:

接诊到急诊病人 300.0
接诊到急诊病人 300.0
接诊到急诊病人 300.0
接诊到急诊病人 300.0
接诊到普通病人 99.99452556343287
接诊到普通病人 99.99419928323131
接诊到普通病人 99.99416696736326

通过输出我们发现,普通病情和急诊病情是同时发生的,就诊也是持续进行的,但是在前一段时间内,接诊只会治疗急诊病人,等急诊病人完诊后,才会接诊普通病人,并且在多线程下是运行良好的。

4. 总结

优先队列是可排序的队列,可以打破先进先出的规则,在一些排序场景很适用,单线程场景下使用PriorityQueue就可以了,多线程环境请使用PriorityBlockingQueue。

预览图
评论区

索引目录