文档章节

PriorityQueue 的出队操作

编走编想
 编走编想
发布于 2013/06/02 16:03
字数 222
阅读 75
收藏 0

在微博上看了篇文章,“关于PriorityQueue 二叉堆的问题“,然后顺便看了一下 PriorityQueue 的源代码和堆排序。PriorityQueue 在出队时,会将位于数组中第一位的元素,同时也是最小的那个元素返回。之后会将数组中最后一个元素放入数组的第一位,然后进行堆调整。

可见,PriorityQueue 并不是维护一个有序的数组,而是只保证二叉堆的根节点是最小的元素。每一次出队操作都会进行堆调整,但每一次堆调整的时间复杂度都是 O(logn),所以在数据量比较大的时候还是一个不错的选择。

PriorityQueue 的堆排序相关的方法主要有两个:siftUp 和 siftDown。前者是 add、offer 等操作使用,后者是 poll 等操作使用。

© 著作权归作者所有

共有 人打赏支持
编走编想
粉丝 148
博文 127
码字总数 109248
作品 0
海淀
程序员
私信 提问
Java集合--Queue(Java中实现1)

1.2 Java中的实现 上一篇,阐述了队列的实现结构,通过图片的形式让大家有了更进一步的了解。 接下来,我,我们来看看队列在Java具体是如何成仙了,来看下Queue的代码!!! 在Java中,Array...

贾博岩
2017/10/21
0
0
【并发队列】无界阻塞队列DelayQueue 源码解析

内部结构 可重入锁 用于根据delay时间排序的优先级队列 用于优化阻塞通知的线程元素leader 用于实现阻塞和通知的Condition对象 delayed和PriorityQueue delayed是一个具有过期时间的元素 Pr...

Izecson
2018/03/28
0
0
【Java源码】PriorityQueue源码剖析及其应用

第0部分 本文概要 这一篇文章说说PriorityQueue, 之前只知道其底层维护着一个小根堆。 An unbounded priority queue based on a priority heap. The elements of the priority queue are ord...

xidiancoder
2017/09/05
0
0
Java中的优先级队列(一)

优先级队列的介绍 优先队列是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级,优先级最高的元素最先得到服务;优先级相同的元素按照其在优先队列中的顺序得到服务。...

peanutmain
2016/11/20
24
0
优先级队列(PriprityQueue)是一种什么样的数据结构

优先级队列(PriprityQueue)是一种无界队列,基于优先级堆,它的元素根据自然顺序或者通过实现Comparator接口的自定义排序方式进行排序。这篇文章,我们将创建一个Items的优先级队列,基于价...

pumpkinHua
2015/10/19
190
0

没有更多内容

加载失败,请刷新页面

加载更多

携程Apollo统一配置中心的搭建和使用(java)

一.Apollo配置中心介绍 1、What is Apollo 1.1 Apollo简介 Apollo(阿波罗)是携程框架部门研发的开源配置管理中心,能够集中化管理应用不同环境、不同集群的配置,配置修改后能够实时推送到...

morpheusWB
33分钟前
0
0
远程获得的有趣的linux命令

使用这些工具从远程了解天气、阅读资料等。 我们即将结束为期 24 天的 Linux 命令行玩具日历。希望你有一直在看,如果没有,请回到开始,从头看过来。你会发现 Linux 终端有很多游戏、消遣和...

Linux就该这么学
47分钟前
6
0
聊聊flink的AsyncWaitOperator

序 本文主要研究一下flink的AsyncWaitOperator AsyncWaitOperator flink-streaming-java_2.11-1.7.0-sources.jar!/org/apache/flink/streaming/api/operators/async/AsyncWaitOperator.java ......

go4it
今天
5
0
Java并发编程基础(四)

ThreadGroup 在主线程创建得线程,如果没有给他指定线程组,那么创建的线程,默认和主线程同一个线程组。线程组可以底下可以是线程,也可以实线程组。 构建线程组的方法: private ThreadGr...

chendom
今天
7
0
Scala学习(一)

学习Spark之前需要学习Scala。 参考学习的书籍:快学Scala

柠檬果过
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部