优先级队列

喜欢ヅ旅行 2024-04-01 15:34 90阅读 0赞

**1.** **优先级队列**

**1.1** **概念**

前面介绍过队列， **队列是一种先进先出** **(FIFO)** **的数据结构** ，但有些情况下， **操作的数据可能带有优先级，一般出队**

**列时，可能需要优先级高的元素先出队列** ，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如

果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。

在这种情况下， **数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象** **。这种数**

**据结构就是** **优先级队列** **(Priority Queue)** **。**

JDK1.8 中的 **PriorityQueue** **底层使用了堆这种数据结构** ，而堆实际就是在完全二叉树的基础上进行了一些调整。

**2.1** **堆的概念**

如果有一个 **关键码的集合** **K = \{k0** **，** **k1** **，** **k2** **，** **…** **，** **kn-1\}** ，把它的所有元素 **按完全二叉树的顺序存储方式存储 在一**

**个一维数组中** ，并满足： **Ki <= K2i+1** **且** **Ki<= K2i+2** (Ki >= K2i+1 且 Ki >= K2i+2) i = 0 ， 1 ， 2… ，则 **称为 小堆** ( 或大

堆 ) 。 **将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。**

**堆的性质：**

**堆中某个节点的值总是不大于或不小于其父节点的值** ；

堆总是一棵 **完全二叉树。**

![d9d4802d16aa43ffa5c3adf00bb877c4.png][]

**2.2** **堆的存储方式**

从堆的概念可知， **堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储**

![0981236c06634ebd839d36b5114bc651.png][]

注意：对于 **非完全二叉树，则不适合使用顺序方式进行存储** ，因为为了能够还原二叉树， **空间中必须要存储空节**

**点，就会导致空间利用率比较低** 。

将元素存储到数组中后，可以根据二叉树章节的性质 5 对树进行还原。假设 i 为节点在数组中的下标，则有：

**如果** **i** **为** **0** **，则** **i** **表示的节点为根节点，否则** **i** **节点的双亲节点为** **(i - 1)/2**

**如果** **2 \* i + 1** **小于节点个数，则节点** **i** **的左孩子下标为** **2 \* i + 1** **，否则没有左孩子**

**如果** **2 \* i + 2** **小于节点个数，则节点** **i** **的右孩子下标为** **2 \* i + 2** **，否则没有右孩子**

**2.3** **堆的创建**

**2.3.1** **堆向下调整**

对于集合 \{ 27,15,19,18,28,34,65,49,25,37 \} 中的数据，如果将其创建成堆呢？

![fe16a5fb46dd48e7943c62cbefcb6bd8.png][]

仔细观察上图后发现： **根节点的左右子树已经完全满足堆的性质，因此只需将根节点向下调整好即可** 。

**向下过程** **(** **以小堆为例** **)** **：**

1. 让 **parent** **标记需要调整的节点** ， **child** **标记** **parent** **的左孩子** ( 注意： parent 如果有孩子一定先是有左孩子 )

2. 如果 parent 的左孩子存在，即 **:child < size** **， 进行以下操作，直到** **parent** **的左孩子不存在**

**parent** **右孩子是否存在，存在找到左右孩子中最小的孩子，让** **child** **进行标**

将 parent 与较小的孩子 child 比较，如果：

parent 小于较小的孩子 child ，调整结束

否则：**交换** **parent** **与较小的孩子** **child** ，交换完成之后， parent 中大的元素向下移动， **可能导致子**

**树不满足对的性质，因此需要继续向下调整，即** **parent = child** **；** **child = parent\*2+1;** **然后继续** **2**

![6157e4b647ab4ed881adf1069ba6b251.png][]

public void shiftDown ( int \[\] array , int parent ) \{

// child 先标记 parent 的左孩子，因为 parent 可能右左没有右

int child = 2 \* parent \+ 1 ;

int size = array . length ;

while ( child < size ) \{

// 如果右孩子存在，找到左右孩子中较小的孩子 , 用 child 进行标记

if ( child \+ 1 < size && array \[ child \+ 1 \] < array \[ child \])\{

child \+= 1 ;

// 如果双亲比其最小的孩子还小，说明该结构已经满足堆的特性了

if ( array \[ parent \] <= array \[ child \]) \{

break ;

\} else \{

// 将双亲与较小的孩子交换

int t = array \[ parent \];

array \[ parent \] = array \[ child \];

array \[ child \] = t ;

// parent 中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整

parent = child ;

child = parent \* 2 \+ 1 ;

**注意：在调整以** **parent** **为根的二叉树时，必须要满足** **parent** **的左子树和右子树已经是堆了才可以向下调整。**

**时间复杂度分析：**

**最坏的情况** 即图示的情况， **从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为** ![a7d4268273264e13931c2acbc08f31a2.png][]

**2.3.2** **堆的创建**

那对于普通的序列 \{ 1,5,3,8,7,6 \} ，即根节点的左右子树不满足堆的特性，又该如何调整呢？

![9a2570e969d348dfa771c7ecb7bb2890.png][]

参考代码：

public static void createHeap ( int \[\] array ) \{

// 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整

int root = (( array . length \- 2 ) >> 1 );

for (; root >= 0 ; root \-- ) \{

shiftDown ( array , root );

**2.3.3** **建堆的时间复杂度**

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明 ( 时间复杂度本来看的就是

近似值，多几个节点不影响最终结果 ) ：

![fdf66ed92ab34fed8d259cd994cb58cc.png][]

因此： **建堆的时间复杂度为O(N)**

**2.4** **堆的插入与删除**

**2.4.1** **堆的插入**

堆的插入总共需要两个步骤：

**1.** **先将元素放入到底层空间中** **(** **注意：空间不够时需要扩容** **)**

**2.** **将最后新插入的节点向上调整，直到满足堆的性质**

![8ca2ee0ddca9449280ec814e3f557abb.png][]

public void shiftUp ( int child ) \{

// 找到 child 的双亲

int parent = ( child \- 1 ) / 2 ;

while ( child > 0 ) \{

// 如果双亲比孩子大， parent 满足堆的性质，调整结束

if ( array \[ parent \] > array \[ child \]) \{

break ;

else \{

// 将双亲与孩子节点进行交换

int t = array \[ parent \];

array \[ parent \] = array \[ child \];

array \[ child \] = t ;

// 小的元素向下移动，可能到值子树不满足对的性质，因此需要继续向上调增

child = parent ;

parent = ( child \- 1 ) / 1 ;

**2.4.2** **堆的删除**

**注意：堆的删除一定删除的是堆顶元素。** 具体如下：

**1.** **将堆顶元素对堆中最后一个元素交换**

**2.** **将堆中有效数据个数减少一个**

**3.** **对堆顶元素进行向下调整**

![9545028f948547b18964693c656a1065.png][]

**2.5** **用堆模拟实现优先级队列**

public class MyPriorityQueue \{

// 演示作用，不再考虑扩容部分的代码

private int \[\] array = new int \[ 100 \];

private int size = 0 ;

public void offffer ( int e ) \{

array \[ size \++ \] = e ;

shiftUp ( size \- 1 );

public int poll () \{

int oldValue = array \[ 0 \];

array \[ 0 \] = array \[ \-- size \];

shiftDown ( 0 );

return oldValue ;

public int peek () \{

return array \[ 0 \];

1. 下列关键字序列为堆的是 :()

A: 100,60,70,50,32,65 B: 60,70,65,50,32,100 C: 65,100,70,32,50,60

D: 70,65,100,32,50,60 E: 32,50,100,70,65,60 F: 50,100,70,65,60,32

2. 已知小根堆为 8,15,10,21,34,16,12 ，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是 ()

A: 1 B: 2 C: 3 D: 4

4. 最小堆 \[0,3,2,5,7,4,6,8\], 在删除堆顶元素 0 之后，其结果是 ()

A: \[3 ， 2 ， 5 ， 7 ， 4 ， 6 ， 8\] B: \[2 ， 3 ， 5 ， 7 ， 4 ， 6 ， 8\]

C: \[2 ， 3 ， 4 ， 5 ， 7 ， 8 ， 6\] D: \[2 ， 3 ， 4 ， 5 ， 6 ， 7 ， 8\]

\[ 参考答案 \]

1.A 2.C 4.C

**3.** **常用接口介绍**

**3.1 PriorityQueue** **的特性**

Java 集合框架中提供了 **PriorityQueue** 和 **PriorityBlockingQueue** 两种类型的优先级队列， **PriorityQueue** **是线**

**程不安全的，** **PriorityBlockingQueue** **是线程安全的** ，本文主要介绍 PriorityQueue 。

![18a247d73b3e43fd9d4ad2735ba24b69.png][]

关于 PriorityQueue 的使用要注意：

1. 使用时必须导入 PriorityQueue 所在的包，即：

![05f4bebb19df478781f8c757610809e2.png][]

2. PriorityQueue 中放置的 **元素必须要能够比较大小，** **不能插入无法比较大小的对象，否则会抛出**

**ClassCastException** **异常 如果你放入堆的是自定义对象，那么你必须实现comparable接口（并重写compareTo 方法） 或者实现comparator接口（重写compare 方法** **）**

3. 不能 **插入** **null** **对象，否则会抛出** **NullPointerException**

4. **没有容量限制，可以插入任意多个元素，其内部可以自动扩容**

5. **插入和删除元素的时间复杂度为** ![80828915b5014e8dafaa1f3091dd4030.png][]

6. **PriorityQueue** **底层使用了堆数据结构**

7. **PriorityQueue** **默认情况下是小堆** \- \-- 即每次获取到的元素都是最小的元素

**3.2 PriorityQueue** **常用接口介绍**

1. **优先级队列的构造**

此处只是列出了 PriorityQueue 中常见的几种构造方式，其他的学生们可以参考帮助文档。

**import** **java** **.** **util** **.** **PriorityQueue** **;**

![522e1ac2d898457899387650fd105e16.png][]

**而在事实上：当我们去阅读priorityQueue的构造方法的源码中，我们会发现，事实上他的构造方法中存在两个形参，** **第一个是我们要创建的默认容量或者一个有序集合，另一个是我们提供的比较方法（即comparable接口的实现类或者comparator接口的实现类用来规定排序方法，如果没有提供，则默认为空，就会使用默认的比较方法）**

**图示如下：**

![16396ff2322d4fd7b78991d247a87305.png][]

![7f8c0cc3310f48528ff6693f39f39d9c.png][]

static void TestPriorityQueue ()\{

// 创建一个空的优先级队列，底层默认容量是 11

PriorityQueue < Integer > q1 = new PriorityQueue <> ();

// 创建一个空的优先级队列，底层的容量为 initialCapacity

PriorityQueue < Integer > q2 = new PriorityQueue <> ( 100 );

ArrayList < Integer > list = new ArrayList <> ();

list . add ( 4 );

list . add ( 3 );

list . add ( 2 );

list . add ( 1 );

// 用 ArrayList 对象来构造一个优先级队列的对象

// q3 中已经包含了三个元素

PriorityQueue < Integer > q3 = new PriorityQueue <> ( list );

System . out . println ( q3 . size ());

System . out . println ( q3 . peek ());

注意： **默认情况下，** **PriorityQueue** **队列是小堆，如果需要大堆需要用户提供比较器**

**我们关于对comparable接口中的compareTo(Object obj)以及comparator接口中的 compare方法**

**1.compareTo(Object obj)方法**

**return this.\*\*-obj.\*\*\*\*//用this-形参，形成的是升序的排序方式**

**相反，如果是形参减去对象，那么则是形成降序的排序方式**

**2.comparator（Object obj1 Object obj2）**

**return obj1- obj2；**

**同理，用第一个对象减去第二个对象，我们形成的排序方式是升序的排序方式；如果用第二个减去第一个对象，我们所形成的的则是降序的排序方式**

// 用户自己定义的比较器：直接实现 Comparator 接口，然后重写该接口中的 compare 方法即可

class IntCmp implements Comparator < Integer > \{

@Override

public int compare ( Integer o1 , Integer o2 ) \{

return o2 \- o1 ;

public class TestPriorityQueue \{

public static void main ( String \[\] args ) \{

PriorityQueue < Integer > p = new PriorityQueue <> ( new IntCmp ());

p . offffer ( 4 );

p . offffer ( 3 );

p . offffer ( 2 );

p . offffer ( 1 );

p . offffer ( 5 );

System . out . println ( p . peek ());

2. **插入** **/** **删除** **/** **获取优先级最高的元素**

![86fbecbbfc05441d9275c943cf78273e.png][]

![7c13b2cb1d2441c0b183755238b9878b.png][]

static void TestPriorityQueue2 ()\{

int \[\] arr = \{  4 , 1 , 9 , 2 , 8 , 0 , 7 , 3 , 6 , 5 \};

// 一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好

// 否则在插入时需要不多的扩容

// 扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低

PriorityQueue < Integer > q = new PriorityQueue <> ( arr . length );

for ( int e : arr ) \{

q . offffer ( e );

System . out . println ( q . size ()); // 打印优先级队列中有效元素个数

System . out . println ( q . peek ()); // 获取优先级最高的元素

// 从优先级队列中删除两个元素之和，再次获取优先级最高的元素

q . poll ();

System . out . println ( q . size ()); // 打印优先级队列中有效元素个数

System . out . println ( q . peek ()); // 获取优先级最高的元素

q . offffer ( 0 );

System . out . println ( q . peek ()); // 获取优先级最高的元素

// 将优先级队列中的有效元素删除掉，检测其是否为空

q . clear ();

if ( q . isEmpty ())\{

System . out . println ( " 优先级队列已经为空 !!!" );

else \{

System . out . println ( " 优先级队列不为空 " );

注意：以下是 JDK 1.8 中， PriorityQueue 的扩容方式：

private static fifinal int MAX\_ARRAY\_SIZE = Integer . MAX\_VALUE \- 8 ;

private void grow ( int minCapacity ) \{

int oldCapacity = queue . length ;

// Double size if small; else grow by 50%

int newCapacity = oldCapacity \+ (( oldCapacity < 64 ) ?

( oldCapacity \+ 2 ) :

( oldCapacity >> 1 ));

// overflflow-conscious code

if ( newCapacity \- MAX\_ARRAY\_SIZE > 0 )

newCapacity = hugeCapacity ( minCapacity );

queue = Arrays . copyOf ( queue , newCapacity );

private static int hugeCapacity ( int minCapacity ) \{

if ( minCapacity < 0 ) // overflflow

throw new OutOfMemoryError ();

return ( minCapacity > MAX\_ARRAY\_SIZE ) ?

Integer . MAX\_VALUE :

MAX\_ARRAY\_SIZE ;

优先级队列的扩容说明：

**如果容量小于** **64** **时，是按照** **oldCapacity** **的** **2** **倍方式扩容的**

**如果容量大于等于** **64** **，是按照** **oldCapacity** **的** **1.5** **倍方式扩容的**

**如果容量超过** **MAX\_ARRAY\_SIZE** **，按照** **MAX\_ARRAY\_SIZE** **来进行扩容**

**3.3 oj** **练习**

top-k 问题：最大或者最小的前 k 个数据。比如：世界前 500 强公司

class Solution \{

public int \[\] smallestK ( int \[\] arr , int k ) \{

// 参数检测

if ( null == arr || k <= 0 )

return new int \[ 0 \];

PriorityQueue < Integer > q = new PriorityQueue <> ( arr . length );

// 将数组中的元素依次放到堆中

for ( int i = 0 ; i < arr . length ; \++ i )\{

q . offffer ( arr \[ i \]);

// 将优先级队列的前 k 个元素放到数组中

int \[\] ret = new int \[ k \];

for ( int i = 0 ; i < k ; \++ i )\{

ret \[ i \] = q . poll ();

return ret ;

**4.** **堆的应用**

**4.1 PriorityQueue** **的实现**

用堆作为底层结构 **封装优先级队列**

**4.2** **堆排序**

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. **建堆**

升序：建大堆

降序：建小堆

2. **利用堆删除思想来进行排序**

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

![012e93df2de64336b6d0c8d4e87d4c0c.png][]

![3b10ae8cb3c44fc8ae71463e93dc68fd.png][]

**4.3 Top-k** **问题**

**TOP-K** **问题：即求数据集合中前** **K** **个最大的元素或者最小的元素，一般情况下数据量都比较大** 。

1. 一组记录排序码为 (5 11 7 2 3 17), 则利用堆排序方法建立的初始堆为 ()

A: (11 5 7 2 3 17) B: (11 5 7 2 17 3) C: (17 11 7 2 3 5)

D: (17 11 7 5 3 2) E: (17 7 11 3 5 2) F: (17 7 11 3 2 5)

答案： C

比如：专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。

对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 ( 可能数据都

不能一下子全部加载到内存中 ) 。最佳的方式就是用堆来解决，基本思路如下：

1. **用数据集合中前** **K** **个元素来建堆**

前 k 个最大的元素，则建小堆

前 k 个最小的元素，则建大堆

2. **用剩余的** **N-K** **个元素依次与堆顶元素来比较，不满足则替换堆顶元素**

将剩余 N-K 个元素依次与堆顶元素比完之后，堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。

**【具体代码实现，见下个课件】**

[d9d4802d16aa43ffa5c3adf00bb877c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/69b94957173843bdbbbccbbd2354c016.png
[0981236c06634ebd839d36b5114bc651.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/81983e28eae84feea42947015bc43053.png
[fe16a5fb46dd48e7943c62cbefcb6bd8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d6a7b0de72d54c9aa6b0a6e1ad856825.png
[6157e4b647ab4ed881adf1069ba6b251.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/5561ed43d985470fb4b23d7d35647064.png
[a7d4268273264e13931c2acbc08f31a2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f229202a4c924a5d9eafab94ac3564ca.png
[9a2570e969d348dfa771c7ecb7bb2890.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/399b1c04ae09432080c839a2d6308bea.png
[fdf66ed92ab34fed8d259cd994cb58cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/5910ad7678bc45659d2cfaf62f748ea2.png
[8ca2ee0ddca9449280ec814e3f557abb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/14ab5faa624d426fb4f2027ca029da57.png
[9545028f948547b18964693c656a1065.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/bb8dea519db0408e973ffadb7da83274.png
[18a247d73b3e43fd9d4ad2735ba24b69.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/7ac4c9d840b644cb9ba1bc9b3e35182d.png
[05f4bebb19df478781f8c757610809e2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/299188e16c5f48ebae13af3e05cb093c.png
[80828915b5014e8dafaa1f3091dd4030.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/eef7d57770aa4019b190daa81d285970.png
[522e1ac2d898457899387650fd105e16.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/00292c73711142b69cadfdf6722340e6.png
[16396ff2322d4fd7b78991d247a87305.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/665d2a01f98546aa820fea089e30fc62.png
[7f8c0cc3310f48528ff6693f39f39d9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/6846315133c4434c901439fa4d9d8f72.png
[86fbecbbfc05441d9275c943cf78273e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b5171ff1ae9e4cc4baf948a7f96a0a75.png
[7c13b2cb1d2441c0b183755238b9878b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b89e9642cf364edd8abe0cfc0f3ddf4f.png
[012e93df2de64336b6d0c8d4e87d4c0c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/1372dbbd31db49d187756a430c98d6a5.png
[3b10ae8cb3c44fc8ae71463e93dc68fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/8cc9ae39dc8443998f3c6455f62d05c3.png