欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[PriorityQueue/Java]PriorityQueue(优先队列)

程序员文章站 2022-07-08 18:00:14
1. 堆(Heap)、完全二叉树、堆排序1.1 堆(Heap)的定义从堆的定义可以看出,堆的实质是满足如下性质的完全二叉树:二叉树中任一非叶子结点均小于(大于)它的孩子结点1.2 完全二叉树树中的结点按从上大小,一层一层,每层从左到右来编号。1.3 堆排序若在输出堆顶的最小值(最大值)后,使得剩余n-1个元素的序列重新又建成一个堆,则得到n个元素的次小值(次大值)…如此反复,便能得到一个有序序列,这个过程称之为堆排序。2. PriorityQueue(优先队列)优先队列是堆排序的应用...

1. 堆(Heap)、完全二叉树、堆排序

1.1 堆(Heap)的定义

[PriorityQueue/Java]PriorityQueue(优先队列)
从堆的定义可以看出,堆的实质是满足如下性质的完全二叉树二叉树中任一非叶子结点均小于(大于)它的孩子结点

1.2 完全二叉树

[PriorityQueue/Java]PriorityQueue(优先队列)
树中的结点按从上大小,一层一层,每层从左到右来编号。

1.3 堆排序

若在输出堆顶的最小值(最大值)后,使得剩余n-1个元素的序列重新又建成一个堆,则得到n个元素的次小值(次大值)…如此反复,便能得到一个有序序列,这个过程称之为堆排序

2. PriorityQueue(优先队列)

  • 优先队列是堆排序的应用。
    小根堆实现最小优先队列
    大根堆实现最大优先队列

  • 普通队列特点:First-In-First-Out(FIFO) 先进先出

  • 优先队列

    1. 最小优先队列,不管入队列顺序如何,当前最小的元素优先出队列
    2. 最大优先队列,不管入队列顺序如何,当前最大的元素优先出队列
  • 可以用堆(Heap)来实现优先队列

    • 入队操作:每一次入队列就是一次堆的插入操作:在二叉树最后插入入队结点,进行结点调整,使其“上浮”至合适位置。
    • 出队操作:每一次出队列就是一次堆的删除堆顶结点操作,其实就是堆的调整:堆顶元素“出队”,以堆中最后一个元素代替之,不断“筛选”至得到新的堆。
  • 以小根堆为例,示意堆(Heap)的入队和出队
    入队操作:不断上浮至合适位置
    [PriorityQueue/Java]PriorityQueue(优先队列)
    出队操作:不断下滤至合适位置
    [PriorityQueue/Java]PriorityQueue(优先队列)

  • 小根堆的堆顶是整个堆中的最小元素,即可用小根堆实现最小优先队列
    大根堆的堆顶是整个堆中的最大元素,即可用大根堆实现最大优先队列

  • PriorityQueue 初始容量为 11,支持动态扩容。容量小于 64 时,扩容一倍;大于 64 时,扩容 0.5 倍。

3. PriorityQueue常用方法

① boolean isEmpty(): 判断队列是否为空

② boolean add(E e): 将指定元素插入到此优先队列中
③ boolean offer(E e):将指定元素插入到此优先队列中
add()和offer()方法的语义完全相同,都是将指定元素插入到此优先队列中。区别在于当方法失败时前者抛出异常,后者返回false。对于PriorityQueue这两个方法没啥差别。
底层实现:由于新加入的元素可能会破坏堆的性质,需要将入队元素(在二叉树最后插入入队结点)“上浮”至合适位置。
时间复杂度 O ( l o g N ) O(logN) O(logN)

④ E element() :获取但不删除此队列的首元素,如果此队列为空,则抛出异常
⑤ E peek() :获取但不删除此队列的首元素,如果此队列为空,则返回null
element()和peek()方法的语义完全相同,都是获取但不删除此队列的首元素。区别在于当方法失败时前者抛出异常,后者返回null。
底层实现:由于堆用数组表示,可以根据下标,下标为0的元素即为堆顶元素,即返回数组索引为0的元素即可。
时间复杂度 O ( 1 ) O(1) O(1)

⑥ E remove():获取并删除此队列的首元素,如果此队列为空,则抛出异常
⑦ E poll() :获取并删除此队列的首元素,如果此队列为空,则返回null
remove()和poll()方法的语义完全相同,都是获取并删除此队列的首元素,区别是当方法失败时前者抛出异常,后者返回null。
底层实现:由于删除操作会改变队列的结构,为维护堆的性质,需要进行堆的调整:堆顶元素“出队”,以堆中最后一个元素代替之,不断“筛选”至得到新的堆。
时间复杂度 O ( l o g N ) O(logN) O(logN)

⑧ E remove(Object o):删除此指定元素的单个实例(如果存在)。即删除此队列中和o相等的某一个元素(如果存在多个相等,则只删除一个)。
底层实现:由于删除操作会改变队列的结构,为维护堆的性质,需要进行堆的调整:堆顶元素“出队”,以堆中最后一个元素代替之,不断“筛选”至得到新的堆。又由于删除元素的位置是任意的,所以调整过程较为繁琐,可分为:1. 若删除的是最后一个元素,直接删除即可。2. 若删除的不是最后一个元素,以删除结点为首元素的子堆进行堆的调整
时间复杂度 O ( N ) O(N) O(N)

本文地址:https://blog.csdn.net/KKKKKKOBE_24/article/details/109151413