目录

优先级队列
优先级队列的应用场景举例
优先队列的底层实现
习题

一 优先级队列
优先级队列也是个队列，因此也是提供以下接口
int size(); // 元素的数量
boolean isEmpty(); // 是否为空 
void enQueue(E element); // 入队 
E deQueue(); // 出队
E front(); // 获取队列的头元素 
void clear(); // 清空


普通的队列是 FIFO 原则，也就是
优先级队列则是按照优先级高低进行出队，比如将优先级最高的元素作为队头优先出队
二 优先级队列的应用场景举例
医院的夜间门诊

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

操作系统的多任务调度

队列元素是任务
优先级是任务类型


作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！

推荐阅读
iOS开发——最新 BAT面试题合集（持续更新中）
三 优先队列的底层实现
根据优先队列的特点，很容易想到:可以直接利用二叉堆作为优先队列的底层实现
可以通过Comparator 或Comparable 去自定义优先级高低

PriorityQueue.m

@implementation PriorityQueue {
    BinaryHeap *_heap;
}

- (instancetype)init {
    self = [super init];
    if (self) {
        _heap = [[BinaryHeap alloc] init];
    }
    return self;
}

- (int)size {
    return _heap.size;
}

- (BOOL)isEmpty {
    return _heap.isEmpty;
}

- (void)clear {
    [_heap clear];
}

- (void)enQueue:(id)element {
    [_heap add:element];
}

- (id)deQueue {
    return [_heap remove];
}

- (id)front {
    return _heap.get;
}



测试代码

- (void)test1 {
    PriorityQueue *queue = [[PriorityQueue alloc] init];   
    [queue enQueue:@(2)];
    [queue enQueue:@(10)];
    [queue enQueue:@(5)];
    [queue enQueue:@(15)];

    while (!queue.isEmpty) {
        NSLog(@"%@",queue.deQueue);
    }
}



打印结果

2020-03-14 11:23:05.140855+0800 17_PriorityQueue[62348:7767683] 15
2020-03-14 11:23:05.141015+0800 17_PriorityQueue[62348:7767683] 10
2020-03-14 11:23:05.141116+0800 17_PriorityQueue[62348:7767683] 5
2020-03-14 11:23:05.141208+0800 17_PriorityQueue[62348:7767683] 2


四 习题


数组中的第K个最大元素


根据字符出现频率排序


数据流中的第K大元素


有序矩阵中第K小的元素


前K个高频元素


前K个高频单词


查找和最小的K对数字


合并K个排序链表



项目链接地址 - 17_PriorityQueue


作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！

以下资料在群文件可自行下载！

推荐阅读
iOS开发——最新 BAT面试题合集（持续更新中）
作者：路飞_Luck

链接：https://www.jianshu.com/p/c3600db997ed

来源：简书

优先级队列（Priority Queue）
优先级队列简介
普通队列与优先级队列对比：
优先级队列应用场景：
优先队列的底层实现
二叉堆实现优先级队列代码
练习

优先级队列简介
优先级队列也属于队列，因此也提供以下接口：
public interface Queue<E> {

	int size();	// 元素的数量
	
	boolean isEmpty();	// 是否为空
	
	void enQueue(E element);	// 入队
	
	E deQueue();	// 出队
	
	E front();	// 获取队列的头元素
	
	void clear();	// 清空
}


普通队列与优先级队列对比：


普通的队列是 FIFO 原则，也就是先进先出


优先级队列则是按照优先级高低进行出队，

比如将优先级最高的元素作为队头优先出队。


优先级队列应用场景：


医院的夜间门诊

队列元素是病人

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


操作系统的多任务调度

队列元素是任务

优先级是任务类型


优先队列的底层实现
利用二叉堆作为优先队列的底层实现
可以通过 Comparator 或 Comparable 去自定义优先级高低


二叉堆实现优先级队列代码
利用二叉堆实现优先级队列。
/**
 * 二叉堆实现优先级队列
 * @author yusael
 */
public class PriorityQueue<E> {
	private BinaryHeap<E> heap;
	
	// 通过 comparator 自定义优先级高低
	public PriorityQueue(Comparator<E> comparator) {
		heap = new BinaryHeap<>(comparator);
	}
	
	public PriorityQueue() {
		this(null);
	}
	
	public int size() {
		return heap.size();
	}

	public boolean isEmpty() {
		return heap.isEmpty();
	}
	
	public void clear() {
		heap.clear();
	}

	public void enQueue(E element) {
		heap.add(element);
	}

	public E deQueue() {
		return heap.remove();
	}

	public E front() {
		return heap.get();
	}
}

练习
◼ 数组中的第K个最大元素：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
◼ 根据字符出现频率排序：https://leetcode-cn.com/problems/sort-characters-by-frequency/
◼ 数据流中的第K大元素：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/
◼ 有序矩阵中第K小的元素：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/
◼ 前K个高频元素：https://leetcode-cn.com/problems/top-k-frequent-elements/
◼ 前K个高频单词：https://leetcode-cn.com/problems/top-k-frequent-words/
◼ 查找和最小的K对数字：https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/
◼ 合并K个排序链表：https://leetcode-cn.com/problems/merge-k-sorted-lists/

应用的场景：主要的就是生产者的生产速度大于消费速度，如果低于那么优先就没有任何的意义了

优先级队列的实现主要有两个方面：队列的优先级  发送消息时的优先这两个问题

代码是在spriingboot整合rabbitmq基础上改造过来的，创建队列时，给队列设置一个优先级
/**
     * 直连的队列名称
     * @return
     */
    @Bean
    public Queue testDirectQueue(){
        /**
         * dureable:是否持久化，默认是false， 持久化队列： 会被存储在磁盘上，当消息代理重启时仍然存在
         * exclusive: 默认也是false，只能被当前创建的连接使用，而且当连接关闭后队列会被关闭
         * autoDelete:是否自动删除，当没有生产者或者消费者使用队列，该队列会自动删除
         * return new Queue("testDirectQueue", true, true, fasle,)
         */
        Map<String, Object> map = new HashMap<>();
        //在这里配置好队列的优先级0-10  默认的是5 注意这里Map中的key需要注意下，是否正确的
        map.put("x-max-priority", 10);
        return new  Queue("firstQueue", true, false,false,map);
    }

在发送消息时，给消息设置下优先级：
@RequestMapping(value = "sendMessage", method = RequestMethod.GET)
    public String sendDirectMessage(){
        //现在发送一个map的消息过去
        String messageId = UUID.randomUUID().toString();
        String messageData = "test message, hello";
        //将lcoaldateTime转换为string类型的
        String format = LocalDateTime.now().format(DateTimeFormatter.ofPattern("yyyy-MM-dd"));
        Map<String, Object> map = new HashMap<>();
        map.put("messageId", messageId);
        map.put("messageData", messageData);
        map.put("createTime", format);
        rabbitTemplate.convertAndSend("exchange", "testDirectRouting", map, new MessagePostProcessor() {

            //这里给消息设置优先级
            @Override
            public Message postProcessMessage(Message message) throws AmqpException {

                //设置消息的优先级别为最大的
                message.getMessageProperties().setPriority(10);
                return message;
            }
        });
        return "ok";
    }


死信队列：

死信队列的场景主要是用来确保重要的业务数据能够记录下来，同时不需要再次入队操作

实现死信队列的流程比较简单：首先就是定义好队列，交换机（包括死信队列，死信交换机） 这里说明下死信队列就是平常的队列并不特殊，死信交换也是如此
@SpringBootConfiguration
public class DeadLetterConfig {


    /**
     * 声明一个业务的交换机
     * @return
     */
    @Bean("businessExchange")
    public FanoutExchange businessExchange(){
        return new FanoutExchange("businessExcahnge");
    }


    /**
     * 声明一个死信交换机
     * @return
     */
    @Bean("deadLetterExchange")
    public FanoutExchange deadLetterExchange(){
        return new FanoutExchange("deadLetterExchange", false, false );
    }


    /**
     * 声明一个业务队列
     * @return
     */
    @Bean("businessQueueA")
    public Queue businessQueueA(){
        Map<String, Object> map = new HashMap(2);
        //队列绑定一个死信交换机属性
        map.put("x-dead-letter-exchange", "deadLetterExchange");
        //给队列中的死信路由键设置一个值
        map.put("x-dead-letter-routing-key", "deadLeeterA");
        //声明一个队列
        return new Queue("businessQueueA", true, false, false, map);
    }


    /**
     * 声明另外一个队列，不同于上面的队列
     * 他们之间的区别是，设置同意死信交换机
     * 但是设置不同的routyKey值
     * @return
     */
    @Bean("businessQueueB")
    public Queue businessQueueB(){
        Map<String, Object> map = new HashMap(2);
        //同上面那个队列一样，声明并且设置一些属性,绑定同一个死信交换机，设置不同的routyKey
        //队列绑定一个死信交换机属性，注意这是以个交换机名称
        map.put("x-dead-letter-exchange", "deadLetterExchange");
        //给队列中的死信路由键设置一个值
        //其实这个路由值是没有任何用的，因为是Fanout类型的交换机
        map.put("x-dead-letter-routing-key", "deadLeeterB");
        return new Queue("businessQueueB", true, false, false, map);
    }

    /**
     * 设置一个死信队列，但是它并没有其他的属性
     * @return
     */
    @Bean("deadLetterQueueA")
    public Queue deadLetterQueueA(){
        return new Queue("deadLetterQueueA", true, false, false);
    }

    /**
     * 设置好另外一个死信队列
     * @return
     */
    @Bean("deadLetterQueueB")
    public Queue deadLetterQueueB(){
        return new Queue("deadLetterQueueB", true, false,false);
    }


    /**
     * 绑定一个业务队列与业务交换机的绑定
     * 这里是只能设置一个routyKey值的
     * @return
     */
    @Bean("bindBusinessA")
    Binding bindbusinessQueueA(){
        return BindingBuilder.bind(businessQueueA()).to(businessExchange());
    }


    /**
     * 绑定queueB与交换
     * @return
     */
    @Bean("bindBusinessB")
    Binding bindBusinessQueueB(){
        return BindingBuilder.bind(businessQueueB()).to(businessExchange());
    }


    /**
     * 指定队列与Fanout交换机之间的绑定
     * @return
     */
    @Bean
    Binding bindingDeadWithExchange(){
        return BindingBuilder.bind(deadLetterQueueA()).to(deadLetterExchange());
    }


    /**
     * 将死信队列与死信交换机进行绑定
     * @return
     */
    @Bean
    Binding bindingDeadB(){
        return BindingBuilder.bind(deadLetterQueueB()).to(deadLetterExchange());
    }

第二步就是在消费队列时进行的代码：
@Slf4j
@Component
public class DeadLetterLlistener {

    /**
     * 监听队列名
     * 接收到业务队列的消息
     */
    @RabbitListener(queues = "businessQueueA")
    public void receive(Message message, Channel channel) throws IOException {
        /**
         * 死信消息的原理：
         * 如果队列配置了参数 x-dead-letter-routing-key 的话，“死信”的路由key将会被替换成该参数对应的值。如果没有设置，则保留该消息原有的路由key。
         * 举例：如果原有消息的路由key是testA，被发送到业务Exchage中，然后被投递到业务队列QueueA中，
         * 如果该队列没有配置参数x-dead-letter-routing-key，则该消息成为死信后，将保留原有的路由keytestA，如果配置了该参数，
         * 并且值设置为testB，那么该消息成为死信后，路由key将会被替换为testB，然后被抛到死信交换机中。
         */
        String msg  = new String(message.getBody());
        log.info("接收到的消息为:{}", msg);
        boolean ack = true;
        Exception exception = null;
        try {
            if (msg.contains("deadletter")){
                throw new RuntimeException("dead letter exception");
            }
        }catch (Exception e){
            ack = false;
            exception = e;
        }

        /**
         * 消息成为死信的几个先决条件：
         * 1:消息是被否定确认(具体就是指：basicNack()或者是basicReject)
         * 2:消息中的requeue属性是被确认为false的
         * 3:具体的成为死信的原因有如下几个：过期消息， 超过规定的队列长度  消费者在进行消费时出现异常
         */
        if (!ack){
            log.info("消息消费发生异常，error msg:{}", exception.getStackTrace());
            //这个方法为不确认该tag对应的消息，b 代表的是确认多条数据信息 b1代表的requeue重新入列
            //这个方法代表的就是将消息丢弃到死信队列中去处理
            channel.basicNack(message.getMessageProperties().getDeliveryTag(),false,false);
        }else{
            //肯定消息消费的方法，第二个参数代表的就是确认多个消息
            channel.basicAck(message.getMessageProperties().getDeliveryTag(), false);
        }
    }


    /**
     * 接收到业务队列的方法B
     * @param message
     * @param channel
     * @throws IOException
     */
    @RabbitListener(queues = "businessQueueB")
    public void receiveB(Message message, Channel channel) throws IOException {
        System.out.println("接收到的信息数据为:" + new String(message.getBody()));
        //此方法代表的就只是将消息做手动确认处理
        channel.basicAck(message.getMessageProperties().getDeliveryTag(), false);
    }


    /**
     * 接收到死信队列的信息方法
     * @param message
     * @param channel
     * @throws IOException
     */
    @RabbitListener(queues = "deadLetterQueueA")
    public void receiveDead(Message message, Channel channel) throws IOException {
        System.out.println("接收到死信队列的消息数据为：" + new String(message.getBody()));
        channel.basicAck(message.getMessageProperties().getDeliveryTag(), false);
    }


    @RabbitListener(queues = "deadLetterQueueB")
    public void receiveDeadB(Message message, Channel channel) throws IOException {
        System.out.println("queueB接收到信息数据为：" + new String(message.getBody()));
        /**
         * x-first-death-exchange:第一次死信所在的交换机名称
         * x-first-death-reason: 成为死信的原因
         * x-first-death-queue： 第一次成为死信所在的队列
         */
        log.info("死信队列中的信息为：{}", message.getMessageProperties());
        channel.basicAck(message.getMessageProperties().getDeliveryTag(), false);
    }

优先级队列的定义应用场景非常广泛，因为很多时候我们需要处理有序的元素，但是不一定要求全部的元素排序，这时候优先级队列就很适合。基于堆的优先级队列能高效的实现插入和删除操作，下面给出基于数组和堆的优先级队列。

基于堆优先级队列

public class MaxPQ <K extends Comparable<K>> {

    private K[] pq;
    private int N = 0;

    public MaxPQ(int maxN) {
        pq = (K[]) new Comparable[maxN+1];
    }

    public boolean isEmpty(){
        return N==0;
    }

    public int size(){
        return N;
    }

    public void insert(K v){
        pq[++N] = v;
        swim(N);
    }

    public K delMax(){
        K max = pq[1];
        exch(1,N--);
        pq[N+1] = null;
        sink(1);
        return max;
    }

    private boolean less(int i,int j){
        return pq[i].compareTo(pq[j]) < 0;
    }

    private void exch(int i,int j){
        K tmp = pq[i];
        pq[i] = pq[j];
        pq[j] = tmp;
    }

    private void swim(int k) {
        while(k>1&&less(k/2,k)){
            exch(k/2,k);
            k/=2;
        }
    }

    private void sink(int k) {
        while(2*k<=N){
            int j = 2*k;
            if(j<N&&less(j,j+1)) j++;
            if(!less(k,j)) break;
            exch(k,j);
            k = j;
        }
    }

    public static void main(String[]args){
        MaxPQ maxPQ = new MaxPQ(10);
        maxPQ.insert(1);
        maxPQ.insert(12);
        maxPQ.insert(10);
        maxPQ.insert(3);
        maxPQ.insert(32);

        while (!maxPQ.isEmpty()){
            System.out.println(maxPQ.delMax());
        }
    }
}