目录概念PriorityQueue的使用小试牛刀（最小k个数）
堆的介绍优先级队列的模拟实现Top-k问题概念优先级队列是一种先进先出（FIFO）的数据结构，与队列不同的是，操作的数据带有优先级，通俗的讲就是可以比较大小，在出队列的时候往往需要优先级最高或者最低的元素先出队列，这种数据结构就是优先级队列（PriorityQueue）
PriorityQueue的使用构造方法这里只介绍三种常用的构造方法构造方法说明PriorityQueue()不带参数，默认容量为11 PriorityQueue(int initialCapacity)参数为初始容量，该初始容量不能小于1 PriorityQueue(Collection c)参数为一个集合
代码展示：
import java.util.ArrayList;import java.util.List;import java.util.PriorityQueue;
public class TestPriorityQueue {public static void main(String[] args) {PriorityQueue PriorityQueue
打印结果：
1，2，3都正常插入，但是插入null的时候，报了NullPointerException空指针异常peek与poll方法的测试 PriorityQueue
打印结果：
默认是小堆，所以堆顶元素是1，获取到1，在删除1，剩余元素个数为两个，当队列为空的时候，这两个方法都返回null size，isEmpty，clear方法的测试 PriorityQueue
打印结果：
打印元素个数为3，所以不为空输出false，清空后，队列为空，输出true注意事项PriorityQueue中存放的元素必须能比较大小，不能比较大小的对象不能插入，会抛出ClassCastException异常例如：向优先级队列中插入两个学生类型的数据class Student {private String name;private int age;
public Student(String name, int age) {this.name = name;this.age = age;}}
public class Test {public static void main(String[] args) {Student s1 = new Student("张三",25);Student s2 = new Student("李四",30);PriorityQueue
如果想比较两个自定类型的大小，请参考Java中对象的比较这篇文章不能插入null对象，否则会抛NullPointerException异常内部可以自动扩容PriorityQueue底层使用堆数据结构PriorityQueue默认是小堆，如果想要创建大堆可以使用如下方式创建： PriorityQueue注意：o2-o1是创建大堆，o1-o2是创建小堆PriorityQueue的扩容方式以下是JDK1.8中扩容的方式：
说明：
如果容量小于64，按照oldCapacity的2倍扩容如果容量大于等于64，按照oldCapacity的1.5倍扩容如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE扩容小试牛刀（最小k个数）
题目
方法：创建一个优先级队列，奖数组中的元素依次放入该优先级队列中，在依次从该优先级队列取出k个即可class Solution {public int[] smallestK(int[] arr, int k) {int[] ret = new int[k];if(k == 0 || arr.length==0){return ret;}PriorityQueue堆的介绍JDK1.8中PriorityQueue底层采用了堆数据结构，堆其实就是对完全二叉树的元素作出了一些调整所谓堆就是将一组数据按照完全二叉树的顺序存储方式存储，保证每一个根结点元素大于它的孩子结点的元素（大根堆）或者小于它的孩子结点的元素（小根堆）
堆的性质堆中某个结点的值总是不大于或着不小于其父节点的值堆是一颗完全二叉树
堆的创建此处我们创建小堆，以21，15，19，17，18，23，25为例
发现上述序列根的左右子树都已经满足小堆的特性，故只需要将根结点向下调整即可
向下调整的过程：
1. 用parent标记要被调整的结点，child标记parent的左孩子2. 如果左孩子存在，即child 方法：从倒数第一个非叶子结点开始调整，直到调整到根 故建堆的时间复杂度为O(N)堆的插入 将元素插入队列尾部，如果空间不够需要扩容将新插入的结点向上调整，直到满足堆的特性例如：给大堆8，7，6，5，1，3插入9 交换堆顶与堆最后一个元素的位置将堆中的有效元素个数减少一个将堆顶元素向下调整 求前k个最大，建小堆求前k个最小，建大堆 求前k个最大，若比堆顶元素大，则替换小堆堆顶元素求前k个最小，若比堆顶元素小，则替换大堆堆顶元素以上就是Java数据结构之优先级队列(PriorityQueue)用法详解的详细内容，更多关于Java优先级队列的资料请关注脚本之家其它相关文章！ 您可能感兴趣的文章:解析Java中PriorityQueue优先级队列结构的源码及用法java优先队列PriorityQueue中Comparator的用法详解Java的优先队列PriorityQueue原理及实例分析Java中关于优先队列PriorityQueue的使用及相关方法Java优先队列(PriorityQueue)重写compare操作Java中优先队列PriorityQueue常用方法示例Java优先队列PriorityQueue超全解析代码展示：
public void shiftDown(int[] array,int parent){int child = parent*2+1;int size = array.length;while(child < size){if(child+1注意：在调整以parent为根的二叉树时，必须满足parent的左右子树满足堆的特性，此时才能向下调整parent时间复杂度分析：最坏情况从根比到叶子，比较的次数为二叉树的高度，故时间复杂度为O(log2N)那么对于普通的序列如1，5，3，8，7，6，即根节点的左右子树不满足大堆的特性，该如何调整？代码展示：
public void createHeap(int[] array){int root = (array.length-2)>>1;for(;root>=0;root--){shiftDown(array,root);}}创建堆的时间复杂度堆的插入分为两步：
代码展示：
public void shiftUp(int[] array,int child){int parent = (child-1)/2;while(child > 0){if(array[child] < array[parent]){break;}else {swap(array,parent,child);child = parent;parent = (child-1)/2;}}}堆的删除堆删除的是堆顶元素删除步骤：
代码展示：
public int poll(){int oldVal = array[0];array[0] = array[array.length-1];size--;shiftDown(array,0);return oldVal;}优先级队列的模拟实现此处用小堆实现优先级队列，并且队列中保存的元素为Integer类型准备工作包括：构造方法，向上调整，向下调整，交换public class MyPriorityQueue {Integer[] array;int size;public MyPriorityQueue(){array = new Integer[11];size = 0;}public MyPriorityQueue(int initCapacity){if(initCapacity < 1){throw new IllegalArgumentException("初始容量小于1");}array = new Integer[initCapacity];size = 0;}public MyPriorityQueue(Integer[] arr){array = new Integer[arr.length];for(int i = 0;i < arr.length;i++){array[i] = arr[i];}size = arr.length;int lastLeafParent = (size-2)/2;for(int root = lastLeafParent;root >= 0;root--){shiftDown(root);}}public void shiftDown(int parent){int child = parent*2+1;while(child < size){if(child+1插入 public boolean offer(Integer e){if(e == null){throw new NullPointerException("插入的元素为null");}ensureCapacity();array[size++] = e;shiftUp(size-1);return true;}private void ensureCapacity(){if(array.length == size){int newCapacity = array.length*2;array = Arrays.copyOf(array,newCapacity);}}注意：插入前需要判断是否扩容，此处扩容按照2倍方式扩容删除 public Integer poll(){if(isEmpty()){return null;}Integer ret = array[0];swap(0,size-1);shiftDown(0);return ret;}获取堆顶元素 public Integer peek(){if(isEmpty()){return null;}Integer ret = array[0];return ret;}获取有效元素个数 public int size(){return size;}判空 public boolean isEmpty(){return size==0;}清空 public void clear(){size = 0;}堆的应用PriorityQueue的实现，PriorityQueue底层采用堆数据结构实现的堆排序，详见基本排序算法总结(Java实现) Top-k问题Top-k问题即求数据中前k个最大或者最小元素，一般情况下数据量都会比较大如果数据量大使用排序那种方法就不可取了，那么如何解决呢？1. 使用数据中前k个数据建堆
2. 用剩余的元素依次与堆顶元素比较