【数据结构】优先级队列（堆）-创新互联
成功就是失败到失败，也丝毫不减当初的热情
目录
1.理解优先级队列
2.优先级队列的底层
2.1 认识堆
2.1.1 堆的概念
2.2.2 堆的存储
2.2 堆的创建
2.2.1 向下调整算法
2.2.2 堆的创建
2.3 堆的插入
2.4 堆的删除
2.5 查看堆顶元素
2.6 堆的运用
3.PriorityQueue
3.1 PriorityQueue 的特性
3.2 PriorityQueue 的构造方法
3.2.1 无参构造方法
3.2.2 指定容量构造方法
3.2.3 用一个集合来创建优先级队列
3.3 PriorityQueue 常用的成员方法
3.4 优先级队列的运用
1.理解优先级队列
在前面博文中我们学习了队列，那我们现在也知道了队列是遵循先进先出原则的一种数据结构。 那接下来我们就一起来学习优先级队列。
优先级队列（PriorityQueue）：顾名思义我们应该就可以想到肯定是队列里面带有优先级，优先级高的数据优先出队。比如：我们平时玩手机的时候，要是有人给你打个电话，页面就会直接跳转到接电话的那个页面，那么也就说明手机来电话的优先级要比手机其他操作的优先级要高。
2.优先级队列的底层在 jdk1.8 版本中，优先级队列的底层其实就是一个堆。
2.1 认识堆 2.1.1 堆的概念堆的概念：堆具有结构性，也就是它是采用数组表示的完全二叉树。堆还具有有序性，也就是根节点大于子节点（或者小于子节点）。
通过根节点大于子节点（或小于子节点），又可以将堆分为大顶堆和小顶堆
大顶堆：又称为大堆，也就是树中所有父节点都要大于或等于子节点
小顶堆：又称为最小堆，也就是树中所有父节点都要小于或等于子节点
堆的存储：数据都是存储在数组中，完全二叉树是我们想象出来的
我们可以通过数组对应的下标，找出二叉树的父子关系：
| 左节点（leftChild） | leftChild = parent * 2 + 1 |
| 右节点（rightChild） | rightchild = parent * 2 + 1 + 1 = leftchild + 1 |
| 父节点（parent） | parent =（child - 1）/ 2 |
向下调整算法前提：用向下调整算法有一个前提就是左右子树必须都是堆，要是建大顶堆左右子树必须都是大顶堆，要是建小顶堆左右子树必须都是小顶堆。
例：建小顶堆，使用向下调整算法，首先左右子树都必须是小顶堆
第一步，先判断左右子树是否都为小顶堆，要是为小顶堆就可以进行第二步向下调整算法
第二步，向下调整算法，找出根结点的左子树和右子树小的那个，然后与根结点比较如果小于根结点就交换（如果不小于，则这整颗数都是小堆不需要交换）。依次循环，直到找到叶子结点终止
例：现在有一个数组里面的元素为{27,15,19,18,26,37}，现在需要将它进行向下调整，成为小顶堆
首先我们将它想成一棵完全二叉树 ：
通过图片，我们可以发现根节点的左右子树都是小根堆，那么接下来我们可以直接使用向下调整算法，使完全二叉树变为小根堆。首先将数组和需要调整节点的下标传给 shiftDown 方法的形参数组 array 和整型 parent ，然后我们可以通过 parent 找到左子节点将左子节点下标存放在 child 变量中。然后判断存放在 child 变量中的左子节点是否存在，如果存在我们就进入循环。然后判断右子节点是否存在，如果存在则判断右子节点是否比左子节点小，要是小就让child存放右子节点的下标。然后在判断 parent 下标对应的值是否小于 child 下标对应的值，如果小于就交换，然后一值循环，直到不小于或者child下标不存在时跳出循环，此时便是小根堆了
//向下调整,建小顶堆，arr是存放数据的数组，size是有效元素的个数
public void shiftDown(int[] arr, int parent) {
int child = parent * 2 + 1;
while (child< size) {
if (child + 1< size && arr[child + 1]< arr[child]) {
child += 1;
}
if (arr[parent]<= arr[child] ) {
break;
} else {
int tmp = arr[parent];
arr[parent] = arr[child];
arr[child] = tmp;
parent = child;//交换之后需要接着向下调整
child = parent * 2 + 1;
}
}
}上面讲解了向下调整算法，如果建大顶堆那么左右子树必须都是大顶堆，如果建小顶堆那么左右子树必须都是小顶堆，这种情况下才能用向下调整算法。
那么对普通的序列，根节点的左右子树不满足堆的特性，又该如何调整呢？
例： 现在有一个数组里面的元素为 {1,5,3,8,7,6}，现在需要将其成为大顶堆
首先我们需要找到最后一个非叶子节点 ，那么它的左右子树肯定是叶子节点，叶子节点没有子节点那么它们就是堆，那我们就可以调用向下调整算法，那么此时最后一棵非叶子节点也就变成了堆，然后我们就依次将每个非叶子节点都通过向下调整算法变成堆，那么此时通过向下调整的非叶子节点也都变成了堆，一直调整到根节点即可变成堆
//建堆，arr是存放数据的数组，size是有效元素的个数
public void buildHeap(int[] arr) {
if (arr == null) {
return;
}
int lastNoLeafNode = (size - 1 - 1) / 2;
while (lastNoLeafNode >= 0) {
shiftDown(arr,lastNoLeafNode);
lastNoLeafNode--;
}
}
//向下调整,建大顶堆
public void shiftDown(int[] arr, int parent) {
int child = parent * 2 + 1;
while (child< size) {
if (child + 1< size && arr[child + 1] >arr[child]) {
child += 1;
}
if (arr[parent] >= arr[child] ) {
break;
} else {
int tmp = arr[parent];
arr[parent] = arr[child];
arr[child] = tmp;
parent = child;
child = parent * 2 + 1;
}
}
}堆的插入操作，也就是将元素插入到堆中的操作，插入后依然满足堆的性质
堆的插入的步骤：
- 第一步： 先将元素插入到数组最后一个元素的后面(注：插入前需要判断是否需要扩容)
- 第二步：将插入的元素依次向上调整，直到满足堆的性质
例如：我们现在有一个数组，数组中的元素为{1,5,3,8,7,6}：
从这个数组和想象出来的完全二叉树我们也就可以看出它是小顶堆，那么现在我们需要插入一个元素 2，应该怎么做呢？
第一步：判断是否需要扩容，然后将 2 插入到数组最后一个元素的后面
第二步：将插入的元素依次向上调整，直到满足堆的性质
注：既然在未插入之前它本来就是个小堆，那么插入得时候只需向上调整即可
//插入，arr 是存储数据的数组，size 是有效元素个数
public void insert(int num) {
if (size >= arr.length) {
grow();
}
arr[size++] = num;
int last = size - 1;
shiftUp(last);
}
//扩容
private void grow() {
arr = Arrays.copyOf(arr,arr.length * 2);
}
//向上调整
public void shiftUp(int child) {
int parent = (child - 1) / 2;
while (child >0) {
//因为本来就是一个小根堆，所以只需将插入得值与父节点的值比较
if (arr[child]< arr[parent]) {
int tmp = arr[child];
arr[child] = arr[parent];
arr[parent] = tmp;
child = parent;
parent = parent = (child - 1) / 2;
} else {
break;
}
}
}堆的删除：一定删除的是堆顶元素
堆的删除步骤：
- 第一步：将堆中最后一个元素赋值给堆顶元素
- 第二步：将堆中的有效元素减一
- 第三步：将堆顶元素向下调整
例如：我们现在有一个数组，数组中的元素为{1,5,3,8,7,6}：
我上面的数组以及图我们可以发现这是一个小顶堆，那么我们现在需要删除它的堆顶元素，删除之后它依然是一个小顶堆，应该怎么做呢？
第一步，将最后一个元素赋值给堆顶元素，有效元素个数减一，就相当于数组中删除了一个元素
第二步，将堆顶元素进行向下调整
//删除，arr 是存储数据的数组，size 是有效元素个数
public int poll() {
int tmp = arr[0];
arr[0] = arr[--size];
shiftDown(arr,0);
return tmp;
}
//向下调整,建小顶堆
public void shiftDown(int[] arr, int parent) {
int child = parent * 2 + 1;
while (child< size) {
if (child + 1< size && arr[child + 1]< arr[child]) {
child += 1;
}
if (arr[parent]<= arr[child] ) {
break;
} else {
int tmp = arr[parent];
arr[parent] = arr[child];
arr[child] = tmp;
parent = child;//交换之后需要接着向下调整
child = parent * 2 + 1;
}
}
}直接返回堆顶值即可
//查看堆顶元素
public int pook() {
return arr[0];
}关于堆操作的代码，阿紫姐姐写的并不是很完善，大家可以自行完善一下，比如每次对堆进行删除和插入之前都进行判空一下等等。
2.6 堆的运用优先级队列的底层其实也就是堆，那我们学习了堆，其实也就相当于学习了优先级队列
堆可以用来进行排序：
- 升序：建大堆
- 降序：建小堆
后面的排序博文中会讲堆排序 ，大家目前先不用管堆排序
3.PriorityQueue 3.1 PriorityQueue 的特性在Java集合框架中其实提供了两种类型的优先级队列分别是 PriorityQueue 和 PriorityBlockingQueue
- PriorityQueue：线程不安全
- PriorityBlockingQueue是线程安全的
那我们本次主要讲解 PriorityQueue
当我们在使用 Java 自带的集合 PriorityQueue 时，需要注意：
- 使用 PriorityQueue 时导入PriorityQueue 所在的包
- PriorityQueue 中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException 异常
- PriorityQueue 中不能插入null对象，否则会抛出 NullPointerException
- PriorityQueue 底层使用了堆数据结构
- PriorityQueue 默认情况下是小堆
默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器
用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
import java.util.Comparator;
class IntCmp implements Comparator{
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
} 目前我们只介绍 PriorityQueue 常用的几种构造方法
3.2.1 无参构造方法创建一个空的优先级队列，默认容量是 11
创建一个初始容量为 initialCapacity 的优先级队列
注意： initialCapacity 不能小于1，否则会抛 IllegalArgumentException 异 常
用一个集合来创建优先级队列
| 方法名 | 功能介绍 |
| boolean offer(E e) | 插入元素，插入成功返回 true ，否则返回 false。如果 e 对象为空，抛出 NullPointerException 异常。空间不够会扩容 |
| E peek() | 查看堆顶元素并返回，如果优先级队列为空则返回null |
| E poll() | 删除堆顶元素并返回，如果优先级队列为空则返回null |
| int size() | 获取优先级队列有效元素的个数 |
| void clear() | 清空优先级队列里面的元素 |
| boolean isEmpty() | 判断优先级是否为空，为空返回true，否则返回false |
在JDK 1.8中，PriorityQueue的扩容方式：
如果容量小于64时，是按照oldCapacity的2倍方式扩容的
如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的
如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容
3.4 优先级队列的运用优先级队列经常用来解决 top-k 的问题。比如：班级前三的同学
接下来我们就用 top-k 完成一道面试题
面试题：最小 k 个数（题目来源：力扣）
题目描述：设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]
思路：题目需要返回数组中的最小的 k 个数，那么我们就可以把数组的前 k 个数构成一个大堆，然后从第 k 个下标开始，依次跟堆顶比较，如果小于堆顶，就删除堆顶的元素，然后插入第 k 下标对应的元素，整个数组都与堆顶比较完后，那么堆里面剩下的就是数组中最小的 k 个数了
import java.util.Comparator;
import java.util.PriorityQueue;
public class Test {
public static void main(String[] args) {
int[] arr = {1,3,5,7,2,4,6,8};
int k = 4;
int[] arrTmp = smallestK(arr,k);
for (int i = 0; i< arrTmp.length; i++) {
System.out.print(arrTmp[i]+" ");
}
}
public static int[] smallestK(int[] arr, int k) {
int[] retArr = new int[k];
for (int i = 0; i< retArr.length; i++) {
retArr[i] = arr[i];
}
PriorityQueuepriorityQueue = new PriorityQueue<>(new IntCmp());
for (int i = 0; i< k; i++) {
priorityQueue.offer(retArr[i]);
}
int t = k;
while (t< arr.length) {
if(priorityQueue.isEmpty()) {
break;
}
int tmp = priorityQueue.peek();
if (arr[t]< tmp) {
priorityQueue.poll();
priorityQueue.offer(arr[t]);
}
t++;
}
for (int i = 0; i< k; i++) {
if (priorityQueue.isEmpty()) {
break;
}
retArr[i] = priorityQueue.poll();
}
return retArr;
}
}
class IntCmp implements Comparator{
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前文章：【数据结构】优先级队列（堆）-创新互联
本文地址：http://myzitong.com/article/dpjgph.html