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-02Java管理系统项目实战入门教程
- 2024-11-02Java监控系统项目实战教程
- 2024-11-02Java就业项目项目实战:从入门到初级工程师的必备技能
- 2024-11-02Java全端项目实战入门教程
- 2024-11-02Java全栈项目实战:从入门到初级应用
- 2024-11-02Java日志系统项目实战:初学者完全指南
- 2024-11-02Java微服务系统项目实战入门教程
- 2024-11-02Java微服务项目实战:新手入门指南
- 2024-11-02Java项目实战:新手入门教程
- 2024-11-02Java小程序项目实战:从入门到简单应用