一. 优先级队列

1.1  优先级队列的概念

优先级队列是一种特殊的队列，它在入队时会根据元素的优先级进行排序，优先级最高的元素排在队列的前面，出队时会优先出队优先级最高的元素。

1.2 优先级队列的区别

（1）与普通队列的区别

1. 普通队列是先进先出的，元素按照入队的顺序依次出队。
2. 优先级队列不考虑入队的先后顺序，只根据元素的优先级来决定出队顺序

（2）与栈的区别

1. 栈是后进先出的，最后入栈的元素最先出栈。
2. 优先级队列则根据优先级决定出队顺序，与入队顺序无关。

核心特点：元素按优先级排序，每次取出优先级最高（或最低）的元素 

二. 堆

PriorityQueue类底层使用堆这种数据结构，堆适用于完全二叉树

2.1 堆的概念

堆是一种特殊的完全二叉树数据结构

完全二叉树：除了最后一层外，每一层的节点数都是满的，并且最后一层的节点都靠左排列。

堆的分类：

（1）最大堆：父节点 ≥ 子节点，根节点为全局最大值。

（2）最小堆：父节点 ≤ 子节点，根节点为全局最小值。

2.2 堆的性质

（1）堆序性：

1. 根节点是堆中的最大元素（大根堆）或最小元素（小根堆）

• 比如：在大根堆中，根节点（第一层）值大于等于第二层子节点的值，第二层子节点的值又大于等于第三层子节点的值，以此类推。

（2）完全二叉树：

1. 所有层（除最后一层）必须完全填满

2. 最后一层的节点必须从左到右连续，不能出现中间空缺

注意：

节点关系	下标计算公式
父节点	parent = (i-1)/2
左子节点	left = 2*i + 1
右子节点	right = 2*i + 2

2.3 堆的操作

（1）向下调整

常用于创建堆和删除操作

主要步骤：

循环条件：子节点的下标小于总数

1. 根据父亲节点找到字节点
2. 比较得出左右节点的最大节点
3. 比较父节点和最大节点，如果左右最大节点大于父节点，则交换
4. 父亲节点等于字节点

代码实现：

    //向下调整public void shiftDown(int i ,int usedSize){int child = (i*2)+1;//左孩子while (child<usedSize) {if (child + 1 < usedSize && elem[child] < elem[child + 1]) {child++;}if (elem[child] > elem[i]) {swap(child,i);i = child;child = (i*2)+1;}else {break;}}}

（2）向上调整

常用于增加操作

 主要步骤：

循环条件：子节点的下标大于0

1. 找出子节点的父亲节点
2. 与父亲节点进行大小比较，大于则交换
3. 让子节点等于父亲

 代码实现：

    //向上调整public void shiftUp(int child){int parent = (child-1)/2;while (child>0) {if (elem[parent] < elem[child]) {swap(parent, child);child = parent;parent = (child - 1) / 2;} else {break;}}}

（3）堆的创建（最大堆）

从最后一个非叶子节点开始，自底向上逐个向下调整

主要步骤：

1. 得到最大下标的父亲节点（最后一个非叶子节点）
2. 向下调整

代码实现： 

 public void createHeap(){//找出最大的根节点for (int i = (usedSize-1-1)/2; i >=0 ; i--) {shiftDown(i,usedSize);}}//向下调整public void shiftDown(int i ,int usedSize){int child = (i*2)+1;//左孩子while (child<usedSize) {if (child + 1 < usedSize && elem[child] < elem[child + 1]) {child++;}if (elem[child] > elem[i]) {swap(child,i);i = child;child = (i*2)+1;}else {break;}}}

（4）堆的插入

主要步骤：

1. 将插入的元素放入最后一位
2. 向上调整
3. 堆的元素个数加一个

代码实现：

    public void offer(int val){if(isFull()){this.elem = Arrays.copyOf(elem,elem.length+1);}else {elem[usedSize] = val;shiftUp(usedSize);usedSize++;}}

注意：必须是在已经有序的基础上插入 

（5）堆的删除

堆的删除是删除栈顶元素

主要步骤：

1. 将栈顶元素和最后一个元素进行交换
2. 堆中的元素总数减少一个
3. 栈顶元素向下调整

 代码实现：

    public int poll(){int tmp = elem[0];swap(0,usedSize-1);usedSize--;shiftDown(0,usedSize);return tmp;}

（6）堆的排序

最大堆——由小到大

主要步骤：

1. 交换堆顶与末尾元素
2. 调整剩余堆
3. 重复直至有序

代码实现：

    //排序从小 到大public void heapSort(){int end = usedSize-1;while(end>0){swap(0,end);shiftDown(0,end);end--;}}

三. PriorityQueue

3.1 PriorityQueue的特性

 注意：

1. PriorityQueue底层使用堆数据结构
2. 默认情况下生成的是最下堆，如果想要生成最大堆可以通过使用比较器
3. 时间复杂度：插入和删除O(log2n)。
4. 堆中不能存放 null对象
5. 堆中存放的元素必须要可以比较
6. 使用时要导入PriorityQueue所在的包

3.2 PriorityQueue的使用

1. 构造方法

(1) 无参构造

Priority( )

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

 注意：无参构造方法，没有给定大小，默认容量为11

(2) 有参构造

PriorityQueue(int initialCapacity)

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

注意：在调用有参构造器时，传入的参数不能小于1，不然会报错

(3) 利用Collection构建

PriorityQueue(Collection <? extends E>c)

import java.util.PriorityQueue;public class Text_1 {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();PriorityQueue<Integer> queue1 = new PriorityQueue<>(100);queue1.offer(12);queue1.offer(3);queue1.offer(9);PriorityQueue<Integer> queue2 =new PriorityQueue<>(queue1);queue2.offer(999);System.out.println(queue2);}
}
//输出：[3, 12, 9, 999]

注意：

在使用PriorityQueue类的时候，不要忘记导入包 

2. 基本操作

（1）插入

插入元素，插入成功返回true，如果插入内容为空，抛出异常

import java.util.PriorityQueue;public class Offer {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(14);queue.offer(2);queue.offer(7);System.out.println(queue);}
}

注意： 空间不够时候会自动进行扩容

（2）删除

移除优先级最高的元素并返回，如果优先级队列为空，返回null

import java.util.PriorityQueue;public class Poll {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(14);queue.offer(2);queue.offer(7);int x = queue.poll();System.out.println(x);}
}

（3）获取

获取优先级最高的元素，如果优先级队列为空，返回null

import java.util.PriorityQueue;public class Peek {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(14);queue.offer(2);queue.offer(7);int x = queue.peek();System.out.println(x);}
}

（4）大小

获取有效元素的个数

import java.util.PriorityQueue;public class Size {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(14);queue.offer(2);queue.offer(7);int x = queue.size();System.out.println(x);}
}

（5）清空

import java.util.PriorityQueue;public class IsEmpty {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(14);queue.offer(2);queue.offer(7);boolean x = queue.isEmpty();System.out.println(x);queue.clear();boolean x1 = queue.isEmpty();System.out.println(x1);}
}

（6）判空

检测优先级队列是否为空，空返回true

import java.util.PriorityQueue;public class IsEmpty {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(14);queue.offer(2);queue.offer(7);boolean x = queue.isEmpty();System.out.println(x);queue.clear();boolean x1 = queue.isEmpty();System.out.println(x1);}
}

3.3 练习

top-k问 题：最大或者最小的前k个数据

求前k最大元素--使用最小堆

求前k最小元素--使用最大堆

（1）求前k个最大元素

方法1：使用最大堆（不推荐，如果数据太多，时间复杂度会很大，很占用内存）

主要步骤：

1. 将数组内所有元素放入优先级队列中
2. 每次删除队列中的最大值
3. 将最大值赋值给新的数组内

    public int[] maxKK(int[] arr, int k) {int[] ret = new int[k];if(arr==null||k<=0){return ret;}//默认最小堆，通过使用比较器，变成默认最大堆PriorityQueue<Integer> queue = new PriorityQueue<>(arr.length);for (int i = 0; i < arr.length; i++) {queue.offer(arr[i]);}//每次弹出的就是最大的for (int i = 0; i < k; i++) {ret[i] = queue.poll();}return ret;}

方法2： 使用最小堆

刷新每一次下限（最小值）

主要步骤：

1. 先将数组内的前k个元素放进优先级队列里
2. 从第k个元素往后开始逐个比较，如果k下标的值比队列的最小值大，那就删除最小元素，添加这个元素
3. 每次都去掉最小的元素，那么就剩下了最大的

    //找出最大的k个数public int[] maxK(int[] array,int k){int[] ret = new int[k];if(k<=0||array == null){return ret;}PriorityQueue<Integer> queue = new PriorityQueue<>(k);for (int i = 0; i < k; i++) {queue.offer(array[i]);}for (int i = k; i < array.length; i++) {int x = queue.peek();if(array[i]>x){queue.poll();queue.offer(array[i]);}}for (int i = 0; i < k; i++) {ret[i] = queue.poll();}return ret;}

（2）求前k个最小元素

使用最大堆

刷新每一次上限（最大值）

主要步骤：

1. 先将数组内的前k个元素放进优先级队列里
2. 从第k个元素往后开始逐个比较，如果k下标的值比队列的最大值小，那就删除最大元素，添加这个元素
3. 每次都去掉最大的元素，那么就剩下了最小的

 public int[] MinK(int[] array,int k){int[] ret = new int[k];if(k<=0||array == null){return ret;}PriorityQueue<Integer> queue = new PriorityQueue<>(new IntCmp());//将数组的前k个元素入队列for (int i = 0; i < k; i++) {queue.offer(array[i]);}for (int i = k; i < array.length; i++) {//队列中的最大值int x = queue.peek();//将最大的弹出去，将这个小的放进来if(array[i] < x){queue.poll();queue.offer(array[i]);}}//将队列中的最大值依次放入数组for (int i = 0; i < k; i++) {ret[i] = queue.poll();}return ret;}

---

点赞的宝子今晚自动触发「躺赢锦鲤」buff！