java中priorityQueue类,java 优先队列

2022-07-31 13:29:03 分类：java 阅读()

　　java中priorityQueue类,java 优先队列

　　00-1010 priority queue概念：介绍用堆小试(最小k数)模拟优先级队列实现Top-k问题

　　00-1010优先级队列是一种先进先出(FIFO)数据结构。与队列不同的是，被操作的数据是有优先级的，也就是说大小可以比较。当离开队列时，具有最高或最低优先级的元素需要首先排队。这种数据结构称为优先级队列。

　　00-1010施工方法

　　这里只介绍三种常见的施工方法。

　　方法描述：PriorityQueue()没有参数，默认容量为11。优先级队列(int initial capacity)的参数是初始容量，不能小于1PriorityQueue(Collection？扩展E c)参数是一个设置代码显示：

　　导入Java . util . ArrayList；导入Java . util . list；导入Java . util . priority queue；公共类TestPriorityQueue { public static void main(String[]args){ PriorityQueueInteger P1=new priority queue()；//默认容量为11 PriorityQueueInteger P2=New priority queue(10)；//参数是初始容量list integer list=new ArrayList()；list . add(0)；list . add(1)；list . add(2)；PriorityQueueInteger P3=new priority queue(list)；//使用集合列表作为参数构造优先级//级别队列}}常用方法

　　方法布尔offer (e e)插入元素e，并返回插入是否成功。如果E为null，则抛出异常E peek()来获取堆的顶部元素(堆将在后面介绍)。如果队列为空，它将返回nullpoll()删除堆的顶部元素，并返回。如果队列为空，则返回nullint size()以获取有效元素的数量void clear()清空队列布尔值is empty()以确定队列是否为空。

　　PriorityQueueInteger p=new priority queue()；p . offer(1)；p . offer(2)；p . offer(3)；system . out . println(p . size())；p.offer(空)；打印结果：

　　正常情况下插入1、2和3，但是当插入null时，会报告NullPointerException null指针异常。

　　使用peek poll方法进行测试

　　PriorityQueueInteger p=new priority queue()；p . offer(1)；p . offer(2)；p . offer(3)；system . out . println(p . peek())；system . out . println(p . poll())；system . out . println(p . size())；p . clear()；system . out . println(p . peek())；system . out . println(p . poll())；打印结果：

　　默认是一个小堆，所以堆的顶层元素是1，得到1，删除1，剩下的元素个数是2。当队列为空时，两种方法都返回null。

　　尺寸测试是一个空的、清晰的方法

　　优先级队列整数p=新优先级队列

　　lt;>(); p.offer(1); p.offer(2); p.offer(3); System.out.println(p.size()); System.out.println(p.isEmpty()); p.clear(); System.out.println(p.isEmpty());打印结果：

　　

 

　　打印元素个数为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<Student> p = new PriorityQueue(); p.offer(s1); p.offer(s2); }}

结果：报了类型转换异常的错误，因为student类型不能直接比较大小

 

　　

 

　　如果想比较两个自定类型的大小，请参考Java中对象的比较这篇文章

　　不能插入null对象，否则会抛NullPointerException异常内部可以自动扩容PriorityQueue底层使用堆数据结构PriorityQueue默认是小堆，如果想要创建大堆可以使用如下方式创建：

 PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2-o1; } });

注意：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<Integer> p = new PriorityQueue<>(arr.length); for(int i = 0;i < arr.length;i++){ p.offer(arr[i]); } for(int i = 0;i < k;i++){ ret[i] = p.poll(); } return ret; }}

 

　　

堆的介绍

JDK1.8中PriorityQueue底层采用了堆数据结构，堆其实就是对完全二叉树的元素作出了一些调整

 

　　所谓堆就是将一组数据按照完全二叉树的顺序存储方式存储，保证每一个根结点元素大于它的孩子结点的元素（大根堆）或者小于它的孩子结点的元素（小根堆）

　　堆的性质

　　堆中某个结点的值总是不大于或着不小于其父节点的值

　　堆是一颗完全二叉树

　　

 

　　堆的创建

　　此处我们创建小堆，以21，15，19，17，18，23，25为例

　　

 

　　发现上述序列根的左右子树都已经满足小堆的特性，故只需要将根结点向下调整即可

　　向下调整的过程：

　　1. 用parent标记要被调整的结点，child标记parent的左孩子

　　2. 如果左孩子存在，即child<size,size为序列元素的个数，进行以下操作，直到左孩子不存在

　　判断parent右孩子是否存在，如果存在让child标记两个孩子最小的孩子如果parent小于child，则将parent与child标记的元素交换位置，如果parent大于child，说明此时已经满足小堆的特性让parent=child，child=parent*2+1，循环步骤2，直到不满足步骤2的条件

 

　　代码展示：

　　

 public void shiftDown(int[] array,int parent){ int child = parent*2+1; int size = array.length; while(child < size){ if(child+1<size && array[child]>array[child+1]){ child = child+1; } if(array[parent] > array[child]){ swap(array,parent,child); parent = child; child = parent*2+1; }else { break; } } }

注意：在调整以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); } }

创建堆的时间复杂度

 

　　

 

　　故建堆的时间复杂度为O(N)

　　堆的插入

　　堆的插入分为两步：

　　将元素插入队列尾部，如果空间不够需要扩容将新插入的结点向上调整，直到满足堆的特性例如：给大堆8，7，6，5，1，3插入9

　　

 

　　代码展示：

　　

 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<size && array[child+1]<array[child]){ child = child+1; } if(array[parent] > array[child]){ swap(parent,child); parent = child; child = parent*2+1; }else { return; } } } public void shiftUp(int child){ int parent = (child-1)/2; while(child > 0){ if(array[child] < array[parent]){ swap(child,parent); child = parent; parent = (child-1)/2; }else { return; } } } public void swap(int a,int b){ int t = array[a]; array[a] = array[b]; array[b] = t; }}

插入

 

　　

 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个数据建堆

　　求前k个最大，建小堆

　　求前k个最小，建大堆

　　2. 用剩余的元素依次与堆顶元素比较

　　求前k个最大，若比堆顶元素大，则替换小堆堆顶元素

　　求前k个最小，若比堆顶元素小，则替换大堆堆顶元素

　　以上就是Java数据结构之优先级队列(PriorityQueue)用法详解的详细内容，更多关于Java优先级队列的资料请关注盛行IT其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

标签：

相关文章阅读

  • java Springboot集成mybatis-plus的方法是什么
  • 浅谈几种Java自定义异常处理方式
  • Java Map所有的值转为String类型
  • java代码中格式化金额 java格式化小数
  • java计算器源代码资源 java计算器简单代码
  • 【java】（一）SpringBoot 源码解析——SpringApplication 初始化（）
  • Spring学习笔记（spring教程 csdn）
  • HDFS Architecture Guide（）
  • 哈工大软件构造Lab3（2022）（哈工大软件构造lab3）
  • nginx基础（nginx基础教程）
  • Java 中HashMap详解(含HashTable, ConcurrentHashMap)（java hashmap使用方法）
  • Java 线程池之Jetty 线程池学习总结（java线程池的使用方法）
  • java线程基础（java 线程教程）
  • 聊聊 Netty 那些事儿之 Reactor 在 Netty 中的实现(创建篇)（）
  • nginx（nginx负载均衡）
    • 留言与评论（共有 条评论）
       
    验证码：