一，了解优先级队列（PriorityQueue）
前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队 列时，可能需要优先级高的元素先出队列。在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数 据结构就是优先级队列(Priority Queue)。
PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整
二，堆的概念
如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一 个一维数组中，并满足：Ki = K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大 堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
三，堆的创建
3.1
（此处为大根堆）
算法思想：
1，让parent标记需要调整的节点，child标记parent的左孩子(注意：parent如果有孩子一定先是有左孩子)
2，如果parent的左孩子存在，即:child < size，进行左右孩子大小判断，确定哪个孩子与parent交换
3，继续向下调整，即parent = child；child = parent*2+1
public class TestHeap { public int[] elem; public int usedSize; public TestHeap( ) { this.elem =new int[10]; } // 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整 public void initElem(int[] array){ for(int i=0;i<array.length;i++){ this.elem[i]=array[i]; usedSize++; } } //向下调整建堆 public void createHeap(){ for(int parent=(usedSize-1-1)/2;parent>=0;parent--){ siftDown(parent,this.usedSize); } } private void siftDown(int parent,int usedSize){ int child=2*parent+1;//左孩子 while(child<usedSize){ if(child+1<usedSize && elem[child] < elem[child+1]){ child++;//如果右孩子比左孩子大，则右孩子和parent交换 } if(elem[child]>elem[parent]){ int tmp=elem[child]; elem[child]=elem[parent]; elem[parent]=tmp; parent=child;//接着往下调整下面的树 child=2*parent+1; }else{ break; } } }建堆时间复杂度为O（N）
3.2堆的插入和删除
堆的插入：
1. 先将元素放入到底层空间中(注意：空间不够时需要扩容)
2. 将最后新插入的节点向上调整，直到满足堆的性质
//插入元素（向上调整） public void push(int val){ if(isFull()){//判满，如果满则扩容 elem= Arrays.copyOf(elem,2*elem.length); } elem[usedSize]=val; siftup(usedSize); usedSize++; } private void siftup(int child){ int parent=(child-1)/2; while(parent>=0){ if(elem[parent]<elem[child]){ int tmp=elem[child]; elem[child]=elem[parent]; elem[parent]=tmp; child=parent; parent=(child-1)/2; }else { break; } } } public boolean isFull(){ return usedSize==elem.length; }堆的删除：
堆的删除一定删除的是堆顶元素。
1. 将堆顶元素对堆中最后一个元素交换
2. 将堆中有效数据个数减少一个
3. 对堆顶元素进行向下调整
//删除元素 public int poll(){ int val=elem[0]; int tmp=elem[0]; elem[0]=elem[usedSize-1]; elem[usedSize-1]=tmp; siftDown(0,usedSize-1); usedSize--; return val; }四，PriorityQueue接口
4.1PriorityQueue相关内容
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线 程不安全的，PriorityBlockingQueue是线程安全的
关于PriorityQueue的使用要注意：
1. 使用时必须导入PriorityQueue所在的包，
2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException异常
3. 不能插入null对象，否则会抛出NullPointerException
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5. 插入和删除元素的时间复杂度为O（logN）
6. PriorityQueue底层使用了堆数据结构
7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素
4.2优先级队列的构造
注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器
class IntCmp implements Comparator<Integer>{ public int compare(Integer o1, Integer o2) { return o2-o1; } } public class TestPriorityQueue { public static void main(String[] args) { PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp()); p.offer(4); p.offer(3); p.offer(2); p.offer(1); p.offer(5); } }4.3插入/删除/获取优先级最高的元素
4.4TopK问题
有k个元素，找出前k个最小元素：
1，整体排序，取出元素
2，建立一个大小为N的小根堆
3，把前k个元素创建为大根堆，遍历剩下的N-k个元素和堆顶元素比较，如果比堆顶元素小，则将堆顶元素删除，当前元素插入
相关题目：https://leetcode.cn/problems/smallest-k-lcci
以第三种思想编写：
class Intcmp implements Comparator<Integer>{ public int compare(Integer o1,Integer o2){ return o2.compareTo(o1);//改为大根堆 } } class Solution { public int[] smallestK(int[] arr, int k) { int[] ret=new int[k]; if(arr==null||k==0){//对arr和k进行基本判断 return ret; } PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(k,new Intcmp());//创建优先队列 for(int i=0;i<k;i++){//将前k个元素放入堆 priorityQueue.offer(arr[i]); } for(int i=k;i<arr.length;i++){//遍历剩余元素 int peekVal=priorityQueue.peek(); if(arr[i]<peekVal){//当前元素和堆顶元素比较，小值放堆顶 priorityQueue.poll(); priorityQueue.offer(arr[i]); } } for(int i=0;i<k;i++){ ret[i]=priorityQueue.poll();//取出剩余堆元素 } return ret; } }五，总结
依旧小结，整体来说堆这一节难度不大，但是还是搞了挺久的，可能冬天到了要冬眠了吧，天天晕晕的。老己不要对自己太好哇！！！如果方便的话请给作者点个赞吧，如文章不全或有问题可私信我哦