深入解析优先级队列与堆结构-育师

一，了解优先级队列（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; } }