数据结构 - 优先级队列（堆）

---

前言

本篇PriorityQueue优先级队列的介绍其底层是堆，关于堆的认识，使用优先级队列能解决的一些问题；如有错误，请在评论区指正，让我们一起交流，共同进步！

---

本文开始

1.介绍优先级队列

优先级队列：它的底层是一种堆的数据结构，它以顺序结构存储，是一个一维数组；

既然底层是堆，就来了解一下！

2. 认识堆

认识堆的特点：有两种堆类型
① 小根堆：父节点小于左右孩子节点，不能保证左右孩子谁大； =》使用优先级队列就创建了小根堆，想要创建大根堆需要自己给比较器(根据自定义规则比较，用于节点交换)；
② 大根堆：父节点大于左右孩子节点，不能保证左右孩子谁大；
③ 堆还是完全二叉树：可以使用顺序存储；非完全二叉树存储，为了还原二叉树还需要存储空节点，浪费空间 - 》堆为什么可以顺序存储的原有；

代码实现小根堆：
向下调整(父节点向下走)：从最后一颗子树开始，父节点与子节点比较大小是否交换，直到不用比较就确定了小根堆；

/*** 建堆的时间复杂度：* O(n)*/
//求出最后一个父节点，因为是顺序存储的-1就是下一颗树的父节点public void createHeap(int[] array) {for (int parent = (usedSize - 1) / 2; parent >= 0; parent--) {//获取最后一个子树父节点，usedSize记录数组中存储的个数//传递父节点和孩子节点最大的范围shiftDown(parent,usedSize);}}/*** root 是每棵子树的根节点的下标*  len  是每棵子树调整结束的结束条件* 向下调整的时间复杂度：O(logn) ;最坏换树的高度*/private void shiftDown(int root,int len) {//向下调整需要每个子树的父节点int child = 2 * root + 1;//求出左孩子节点位置while (child < len) {//获取孩子节点最大值下标//防止右孩子下标越界，需要判断if(child + 1 < len && elem[child] < elem[child + 1]) {child++;}//比较父子节点大小if(elem[child] > elem[root]) {swap(elem,child,root);//调整父子节点下标位置child = root;root = 2 * child + 1;//再次获取左孩子节点下标}else {//父节点大于子节点直接跳出break;}}}//交换函数private void swap(int[] elem, int child, int root) {int tmp = elem[child];elem[child] = elem[root];elem[root] = tmp;}

代码实现大根堆
向上调整(孩子节点向上走)：

private void shiftUp(int child) {//求出它的父节点下标int parent = (child - 1) / 2;//child==0最后一个节点不用比较while (child > 0) {//比较父子节点大小if(elem[child] > elem[parent]) {//交换swap(elem,child,parent);//移动父子节点下标，可能不止移动一次（子节点向上）child = parent;parent = (child - 1) / 2;//获得更上一级的父节点下标}else {//父节点小于子节点直接跳出break;}}
}

3. 实现优先级队列

了解大根堆，小根堆就可以实现优先级队列！
代码实现优先级队列（以大根堆为例）：

public class PriorityQueue {public int[] elem;public int usedSize;public PriorityQueue() {int[] elem = new int[10];}//交换函数private void swap(int[] elem, int child, int root) {int tmp = elem[child];elem[child] = elem[root];elem[root] = tmp;}/*** 入队：仍然要保持是大根堆*/public void push(int val) {//插入if(isFull()) {//扩增Arrays.copyOf(elem,2*elem.length);return;}//没满就在最后位置插入elem[usedSize] = val;//向上调整即可shiftUp(usedSize);usedSize++;}public boolean isFull() {return usedSize == elem.length;}/*** 出队删除：每次删除的都是优先级高的元素* 仍然要保持是大根堆*/public void pollHeap() {if(isEmpty()) {return;}//交换首尾int end = usedSize - 1;swap(elem,0,end);//向下调整范围需要-1，因为删除了一个元素shiftDown(0,--usedSize);}
//判断是否为空public boolean isEmpty() {return usedSize == 0;}/*** 获取堆顶元素*/public int peekHeap() {if(isEmpty()) {return -1;}return elem[0];}
}

3.1 了解优先级队列的构造方法：

① 无参构造：默认大小11

② 有一个整形参数的构造：

③ 两个参数(整形，比较规则)的构造：

3.2 使用优先级队列解决问题：

1.top-k问题：
例如取前k个最小 / 最大的值；
2.堆排序
①升序(1,2,3…)：大根堆
使用原因：大根堆堆顶元素一定最大的，将堆顶元素与堆末尾元素交换，再向下调整，重新得到大根堆；这样每次都会把最大的放到最后，再次到堆顶的时候，堆顶后面的元素已经有序了，依次弹出即可；
②降序(4,3,2…)：小根堆
使用原有：小根堆堆顶元素一定最小的，将堆顶元素与堆末尾元素交换，再向下调整，重新得小根堆；这样每次都会把最小的放到最后，再次到堆顶的时候，堆顶后面的元素已经降序有序了，依次弹出即可；

---

总结

✨✨✨各位读友，本篇分享到内容如果对你有帮助给个👍赞鼓励一下吧！！
感谢每一位一起走到这的伙伴，我们可以一起交流进步！！！一起加油吧！！！