Java的优先队列:PriorityQueue
2021/10/29 22:10:31
本文主要是介绍Java的优先队列:PriorityQueue,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Java的优先队列:PriorityQueue
说明:PriorityQueue算法原理就是通过完全二叉树(complete binary tree)实现的小顶堆(任意一个非叶子节点的权值,都不大于其左右子节点的权值)
代码案例:
/** * 测试Java的优先队列 PriorityQueue * add()和offer()方法,前者在插入失败时抛出异常,后则则会返回false * element()和peek()方法,都是获取但不删除队首元素,当方法失败时前者抛出异常,后者返回null,时间复杂度是O(1) * remove()和poll() 方法,都是获取并删除队首元素,区别是当方法失败时前者抛出异常,后者返回null, * 由于删除操作会改变队列的结构,为维护小顶堆的性质,需要进行必要的调整,故时间复杂度是O(n) */ @Test public void testPriorityQueue() { //创建多个Goods对象 List<Goods> goodsList = Lists.newArrayList(); for (int i = 0; i < 5; i++) { Goods goods = new Goods(); goods.setGoodId((long) i); goods.setGoodPrice("50" + i); goodsList.add(goods); } //打乱顺序 Collections.shuffle(goodsList); //打印打乱后的结果 System.out.println("打乱后的结果:" + JackSonUtil.objToJson(goodsList)); //定义一个优先队列,并指定价格是比较准则 PriorityQueue<Goods> priorityQueue = new PriorityQueue<>(Comparator.comparing(Goods ::getGoodPrice)); //将元素加入进去 priorityQueue.addAll(goodsList); //全部打印这个队列 System.out.println("priorityQueue = " + JackSonUtil.objToJson(priorityQueue)); //一个个输出这个队列 System.out.println("----------priorityQueue一个个弹出-----------"); System.out.println(JackSonUtil.objToJson(priorityQueue.poll())); System.out.println(JackSonUtil.objToJson(priorityQueue.poll())); System.out.println(JackSonUtil.objToJson(priorityQueue.poll())); System.out.println(JackSonUtil.objToJson(priorityQueue.poll())); System.out.println(JackSonUtil.objToJson(priorityQueue.poll())); System.out.println(JackSonUtil.objToJson(priorityQueue.poll())); }
每一次的新加入元素,都会调整这个二叉树,以保证小顶堆特性,poll
命令则将顶部的最小元素弹出,而后重新调整二叉树,再次使用poll
就会将次小元素弹出,也就是说,本身并不是排序,只有使用的时候才会将顺序弹出。
应用: 可以应用于选择最小、次小、第三小的值产品的情况
参考文章:
《JAVA中PRIORITYQUEUE详解》
这篇关于Java的优先队列:PriorityQueue的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门:从零开始的编程之旅
- 2024-11-23Java创业入门:新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门:初学者的简单教程
- 2024-11-23JAVA副业入门:初学者的实战指南