精华内容
下载资源
问答
  • 优先级队列的应用场景举例 优先队列的底层实现 习题 一 优先级队列 优先级队列也是个队列,因此也是提供以下接口 int size(); // 元素的数量 boolean isEmpty(); // 是否为空 void enQueue(E element); // 入队 E...
    目录
    • 优先级队列
    • 优先级队列的应用场景举例
    • 优先队列的底层实现
    • 习题
    一 优先级队列

    优先级队列也是个队列,因此也是提供以下接口

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

    普通的队列是 FIFO 原则,也就是

    优先级队列则是按照优先级高低进行出队,比如将优先级最高的元素作为队头优先出队

    二 优先级队列的应用场景举例

    医院的夜间门诊

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

    操作系统的多任务调度

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

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

    推荐阅读

    iOS开发——最新 BAT面试题合集(持续更新中)

    三 优先队列的底层实现

    根据优先队列的特点,很容易想到:可以直接利用二叉堆作为优先队列的底层实现

    可以通过ComparatorComparable 去自定义优先级高低

    • 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
    
    
    四 习题

    项目链接地址 - 17_PriorityQueue


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

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

    推荐阅读

    iOS开发——最新 BAT面试题合集(持续更新中)

    作者:路飞_Luck
    链接:https://www.jianshu.com/p/c3600db997ed
    来源:简书

    展开全文
  • 优先级队列(Priority Queue)优先级队列简介普通队列与优先级队列对比:优先级队列应用场景:优先队列的底层实现二叉堆实现优先级队列代码 优先级队列简介 优先级队列也属于队列,因此也提供以下接口: public ...

    优先级队列简介

    优先级队列也属于队列,因此也提供以下接口:

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

    在这里插入图片描述

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

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

    • 优先级队列则是按照优先级高低进行出队,
      比如将优先级最高的元素作为队头优先出队。

    优先级队列应用场景:

    • 医院的夜间门诊
      队列元素是病人
      优先级是病情的严重情况、挂号时间

    • 操作系统的多任务调度
      队列元素是任务
      优先级是任务类型

    优先队列的底层实现

    利用二叉堆作为优先队列的底层实现

    可以通过 ComparatorComparable 去自定义优先级高低
    在这里插入图片描述

    二叉堆实现优先级队列代码

    利用二叉堆实现优先级队列。

    /**
     * 二叉堆实现优先级队列
     * @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 ...

    应用的场景:主要的就是生产者的生产速度大于消费速度,如果低于那么优先就没有任何的意义了
    优先级队列的实现主要有两个方面:队列的优先级 发送消息时的优先这两个问题
    代码是在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());
            }
        }
    }
    
    展开全文
  • 优先级队列(堆)

    2020-03-22 23:15:38
    优先级队列概念集合框架里的 PriorityQueue特性常用方法优先级队列的模拟实现堆的基本概念:应用场景top-K问题 概念 操作的数据带有优先级,一般出队列时,可能需要优先级高的元素出队 集合框架里的 PriorityQueue ...
  • /** * @author qcg ... * 应用场景: * 1.topK问题 * 2.不需要FIFO按照权重操作出队情况 * 3.RabbitMQ中,当消费者不足,不能及时进行消费情况下,优先级队列会生效 * 4.hadoop中Map结束之后会将IF...
  • 一、队列 public void levelOrder(TreeNode subTree) { Queue queue = new LinkedList(); queue.add(root); while (!queue.isEmpty()) { TreeNode head = queue.remove(); visted(head); if (head.leftChild != n
  • 优先级队列应用场景 优先队列的底层实现(附代码) 优先级队列(Priority Queue) 接口: public interface Queue<E> { int size(); // 元素的数量 boolean isEmpty(); // 是否为空 void enQueue(E...
  • 今天阿笨给大家分享是通过RabbitMQ的优先级消息队列特性来解决我们业务中需要优先处理任务。 1.1、本次分享课程适合人群如下: 1、有一定NET开发基础并对RabbitMQ技术有一定了解和认识。 ...
  • 元素接受访问次序按照优先级,而非FIFO 场景 夜间门诊 病情危急优先治疗 多任务调度 每个任务都有一个指标,指标都是动态变化,操作系统总是挑选指标最大任务交由CPU处理 应用、算法与特点 ...
  • 先思考一个应用场景, ...PriorityBlockingQueue是一个基于优先级堆的无界的并发安全的优先级队列(FIFO),队列的元素按照其自然顺序进行排序,或者根据构造队列时提供的 Comparator 进行排序...
  • 分布式系统不同模块之间的通信,除了远程服务调用以外,消息中间件是另一个重要的手段。...二、消息队列的应用场景 消息队列可以用于系统内部组件之间的通信,也可以用于系统跟其他服务之间的交互...
  • 应用场景:  对于现在计算机来说,同时可以运行多个程序,加上操作系统里面一大堆进程,操作系统经常会处理各个进程排序,从而有条不紊运行各种程序。  在这种情况下,需要一种数据结构且需要以下功能...
  • 1、优先级队列的使用场景 1)、定时任务轮训问题 2)、合并有序小文件 2、求Top K值问题【使用一个堆解决】 3、求中位数、百分位数【使用一个大顶堆一个小顶堆解决】 4、大数据量日志统计搜索排行榜【散列表+堆...
  • PriorityQueue实际应用场景

    千次阅读 2020-02-05 20:06:15
    PriorityQueue 名叫优先级队列,底层由堆结构实现,默认是小根堆。通过 offer 方法添加进去元素会进行堆排序,最小元素放在堆顶。通过 peek 方法可以获得堆顶(最小)元素。通过 poll 方法可以删除堆顶元素同时...
  • 1.优先级队列的实现: 就是将需要先出去的(优先级高的放在最上面的一些应用场景), 与队列来比较?不会。 队列 这个比较常见,生活中的超市排队,叫号系统 树 ①,红黑树:JAVA8中的hashMap满足一定的阈值,自动扩...
  • 数据结构与算法的应用场景

    千次阅读 2017-11-28 20:41:02
    专用数据结构:栈、队列、优先级队列 排序:插入排序、希尔排序、快速排序、归并排序、堆排序 图:邻接矩阵、邻接表 外部存储:顺序存储、索引文件、B-树、哈希方法 2. 通用数据结构应用场景 数组和链表是最...
  • 在许多应用场景中,我们希望YARN作业能够按照优先级的先后顺序来执行。在现有机制下,为了满足这个需求,只能在使用CapacityScheduler时通过创建不同资源量的队列,(优先级越高的队列,资源量越大),然后將...
  •  常常在面试和被面试时候,作为偶尔代替“考官”和经常被面我,时时刻刻都会谈及到线程安全,并发,安全队列,线程池,反射技术,设计模式,场景应用举例,优先级,同步锁,架构设计要素,技术选型,比较相关...
  • Redis简介 redis是用C语言开发的一个基于内存的、高性能key-value键值对...Redis应用场景 介绍几种常见的应用: 构建队列系统 可以用list可以构建队列系统,使用sorted set甚至可以构建有优先级队列系统 pub、sub
  • 算法笔记-堆的应用

    2018-12-28 21:49:02
    优先级队列应用的场景非常多,后续总结数据结构和算法都要依赖于它。比如:赫夫曼编码,图最短路径,最小生成树等等。 举例一:合并有序小文件。 假如有 100 个文件,每个文件 100M,文件中存储都是有序字符串...
  • 的应用

    2019-09-29 23:22:28
    本文主要整理关于堆的应用场景优先级队列、TopK问题、利用堆求中位数
  • 队列

    2020-03-23 00:03:49
    Queue:队列,队头删除,队尾插入 Deque:两端队列,队头、队尾都能插入或...3.PriorityQueue 优先级队列,它内部实现结构可以快速把所有元素中最小的元素单独放出来,最典型的应用场景:任务调度 队列的2个应用场...
  • 关于堆介绍

    2020-05-16 12:25:00
    前言 堆是生产中非常重要也很实用的一种数据...优先级队列的应用场景很广,它是如何实现的呢 如何求 Top K 问题 TP99 是生产中的一个非常重要的指标,如何快速计算 可能你已经猜到了,以上生产上的高频问题都可以用堆来
  • Beanstalkd 是一个高性能消息队列... Beanstalkd 是一个轻量级消息中间件,它最大特点是将自己定位为基于管道 (tube) 和任务 (job) 工作队列 (work-queue):Beanstalkd 支持任务优先级 (priority), 延时 (delay...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 130
精华内容 52
关键字:

优先级队列的应用场景