目录

一. 优先级队列

1.1  优先级队列的概念

1.2 优先级队列的区别

（1）与普通队列的区别

（2）与栈的区别

二. 堆

2.1 堆的概念

2.2 堆的性质

2.3 堆的操作

（1）向下调整

（2）向上调整

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

（4）堆的插入

（5）堆的删除

（6）堆的排序

三. PriorityQueue

3.1 PriorityQueue的特性

3.2 PriorityQueue的使用

1. 构造方法

(1) 无参构造

(2) 有参构造

(3) 利用Collection构建

2. 基本操作

（1）插入

（2）删除

（3）获取

（4）大小

（5）清空

（6）判空

3.3 练习

（1）求前k个最大元素

（2）求前k个最小元素

---

一. 优先级队列

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！