包头市网站建设_网站建设公司_JSON_seo优化

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

五，总结

依旧小结，整体来说堆这一节难度不大，但是还是搞了挺久的，可能冬天到了要冬眠了吧，天天晕晕的。老己不要对自己太好哇！！！如果方便的话请给作者点个赞吧，如文章不全或有问题可私信我哦