优先级队列(堆)

大家好，欢迎来到IT知识分享网。

目录

1.定义

2.性质

3.分类

4.示例代码

5.PriorityQueue(小根堆)-线程不安全

1. 使用注意事项

2. 构造器介绍

3. 使用示例

4. 小根堆改为大根堆

5.如果数据类型为Integer这样的包装类(其源码不能更改),怎么改大根堆?

6.总结

7.扩容问题

​8.常用方法

1.定义

队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。

在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。

简单而言，底层其实就是一颗二叉树，只不过这棵二叉树比较特殊，为完全二叉树，在这个基础上实现的一种结构，这种结构叫做堆。

2.性质

从上面的定义中，我们可以得到堆的性质:

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

2.堆总是一棵完全二叉树。

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

3.分类

小根堆：根节点比左右孩子都小                                       大根堆：根节点比左右孩子都大

4.示例代码

在本次示例代码中，我们将使用向下调整的方法，从最后一个子树的根节点开始局部调整为大根堆，直到整个数组都满足大根堆的性质。

1. 在实现这个数据结构的过程中需要解决的问题两点:

1.1 如何找到最后一课子树的根节点  —-（array.length-1-1）/2

1.2 每颗子树调整的时候，结束位置在哪里  —-  location < array.length

2.示例代码

2.1 大根堆

/ * 大根堆 * * @param array */ public void createHeap(int[] array) { for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) { shiftDown(parent, array); } } / * @param parent 每颗子树的根节点 * @param array 每颗子树调整的结束位置 location < array.length */ public void shiftDown(int parent, int[] array) { int child = 2 * parent + 1; while (child < array.length) { //child + 1 < array.length 保证右孩子 if (child + 1 < array.length && array[child] < array[child + 1]) { child++; } //child下标一定为左右孩子 最大值的下标 if (array[parent] < array[child]) { int tmp = array[parent]; array[parent] = array[child]; array[child] = tmp; parent = child; child = 2 * parent + 1; }else{ break; } } }

2.2 小根堆

/ * 小根堆 * * @param array */ public void createHeap(int[] array) { for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) { shiftDown(parent, array); } } / * @param parent 每颗子树的根节点 * @param array 每颗子树调整的结束位置 location < array.length */ public void shiftDown(int parent, int[] array) { int child = 2 * parent + 1; while (child < array.length) { //child + 1 < array.length 保证右孩子 if (child + 1 < array.length && array[child] > array[child + 1]) { child++; } //child下标一定为左右孩子 最小值的下标 if (array[parent] > array[child]) { int tmp = array[parent]; array[parent] = array[child]; array[child] = tmp; parent = child; child = 2 * parent + 1; }else{ break; } } }

2.3 注意点(以大根堆为例)

2.4 建堆的时间复杂度-O(N)

5.PriorityQueue(小根堆)-线程不安全

其中，PriorityBlockingQueue-线程安全。下面是对PriorityQueue的使用介绍。

1. 使用注意事项

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

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

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

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

• 5. 插入和删除元素的时间复杂度为O(logN)

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

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

2. 构造器介绍

3. 使用示例

class Student { private int age; public Student(int age) { this.age = age; } } public class Main { public static void main(String[] args) { PriorityQueue<Student> priorityQueue = new PriorityQueue<>(); priorityQueue.offer(new Student(20)); priorityQueue.offer(new Student(10)); } }

当我们在IDEA中运行这个代码的时候，代码会报错，报错为:

为什么会出现这个情况呢?我们需要了解在main方法中的三个代码的运行逻辑：

1.PriorityQueue priorityQueue = new PriorityQueue<>();

1.点击PriorityQueue查看源码，查看其默认的数组容量为11

• 点PriorityQueue，查看构造方法

 2.点击this，查看方法，我们需要先了解两个变量的含义

• 比较器设置为null， 当没有传入比较器的时候，那么相当于只是对queue数组进行实例化了

 2. priorityQueue.offer(new Student(20));

 1.执行第二句话，第一次没有产生比较，直接放入零下标

 3.priorityQueue.offer(new Student(10));

1.第二次比较

2.我们需要进入sifUp()方法进行查看，我们发现如果传入的比较器为空，就会调用siftUpComparable(k, x);

3.点击siftUpComparable(k, x);方法，我们会发现会调用key的compareTo方法，但是在Student类中，并没有这个方法，所以会抛出异常

 4.所以我们需要给Student类，重写comparabTo方法

class Student implements Comparable<Student> { private int age; public Student(int age) { this.age = age; } @Override public int compareTo(Student o) { return this.age - o.age; } } public class Main { public static void main(String[] args) { PriorityQueue<Student> priorityQueue = new PriorityQueue<>(); priorityQueue.offer(new Student(20)); priorityQueue.offer(new Student(10)); } }

5.那么在第三行代码中，就会调用Student类的comparabTo方法，并且在这个方法中，没有进入循环，就进行交换了。

 3.priorityQueue.offer(new Student(10));

4. 小根堆改为大根堆

在1.使用注意事项中，我们说过:

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

 那我们应该怎么把其改成大根堆呢?以上面的Student类为例，我们可以改变comparabTo方法，将比较器的相减更换即可，将this.age – o.age换成return o.age- this.age即可。

class Student implements Comparable<Student> { private int age; public Student(int age) { this.age = age; } @Override public int compareTo(Student o) { return o.age- this.age; } } public class Main { public static void main(String[] args) { PriorityQueue<Student> priorityQueue = new PriorityQueue<>(); priorityQueue.offer(new Student(20)); priorityQueue.offer(new Student(10)); } }

5.如果数据类型为Integer这样的包装类(其源码不能更改),怎么改大根堆?

• 传入自己添加定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即

 1.自定义类IntCmp，实现Comparator<Integer>接口

class IntCmp implements Comparator<Integer>{ @Override public int compare(Integer o1, Integer o2) { return o2-o1; } }PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>(new IntCmp());

2.匿名内部类

PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } });

3. lambda表达式

PriorityQueue<Integer> priorityQueue3 = new PriorityQueue<>((x,y)->{return x.compareTo(y);}); PriorityQueue<Integer> priorityQueue4 = new PriorityQueue<>((x,y)-> x.compareTo(y));

6.总结

• 1.当没有传数组容量的时候，默认11；

• 2.当没有传入比较器的时候，他必须是可比较的；

• 3.优先使用的是比较器来比较；

7.扩容问题

小于64，二倍扩容，大于64，1.5扩容

 8.常用方法

其中需要注意:

1.offer-堆的插入

• 1.插入一个数到数组最后面，如果数组不够大，先扩容；

• 2.向上调整

2.poll-堆的删除

• 1.判断是否非空，交换0下标和数组最后一个的值；

• 2.堆的有效数据个数减一；

• 3.向下调整

以上就是优先级队列的所有内容了。