进入网站前如何做环境检测网页设计与制作模板免费

进入网站前如何做环境检测,网页设计与制作模板免费,如何设计网页作业,大连网页设计培训学校一#xff0c;了解优先级队列#xff08;PriorityQueue#xff09; 前面介绍过队列#xff0c;队列是一种先进先出(FIFO)的数据结构#xff0c;但有些情况下#xff0c;操作的数据可能带有优先级#xff0c;一般出队 列时#xff0c;可能需要优先级高的元素先出队列。…一了解优先级队列PriorityQueue前面介绍过队列队列是一种先进先出(FIFO)的数据结构但有些情况下操作的数据可能带有优先级一般出队 列时可能需要优先级高的元素先出队列。在这种情况下数据结构应该提供两个最基本的操作一个是返回最高优先级对象一个是添加新的对象。这种数 据结构就是优先级队列(Priority Queue)。PriorityQueue底层使用了堆这种数据结构而堆实际就是在完全二叉树的基础上进行了一些调整二堆的概念如果有一个关键码的集合K {k0k1 k2…kn-1}把它的所有元素按完全二叉树的顺序存储方式存储 在一 个一维数组中并满足Ki K2i1 且 Ki K2i2) i 012…则称为 小堆(或大 堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。堆的性质堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树。三堆的创建3.1此处为大根堆算法思想1让parent标记需要调整的节点child标记parent的左孩子(注意parent如果有孩子一定先是有左孩子)2如果parent的左孩子存在即:child size进行左右孩子大小判断确定哪个孩子与parent交换3继续向下调整即parent childchild parent*21public class TestHeap { public int[] elem; public int usedSize; public TestHeap( ) { this.elem new int[10]; } // 找倒数第一个非叶子节点从该节点位置开始往前一直到根节点遇到一个节点应用向下调整 public void initElem(int[] array){ for(int i0;iarray.length;i){ this.elem[i]array[i]; usedSize; } } //向下调整建堆 public void createHeap(){ for(int parent(usedSize-1-1)/2;parent0;parent--){ siftDown(parent,this.usedSize); } } private void siftDown(int parent,int usedSize){ int child2*parent1;//左孩子 while(childusedSize){ if(child1usedSize elem[child] elem[child1]){ child;//如果右孩子比左孩子大则右孩子和parent交换 } if(elem[child]elem[parent]){ int tmpelem[child]; elem[child]elem[parent]; elem[parent]tmp; parentchild;//接着往下调整下面的树 child2*parent1; }else{ break; } } }建堆时间复杂度为ON3.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(parent0){ if(elem[parent]elem[child]){ int tmpelem[child]; elem[child]elem[parent]; elem[parent]tmp; childparent; parent(child-1)/2; }else { break; } } } public boolean isFull(){ return usedSizeelem.length; }堆的删除堆的删除一定删除的是堆顶元素。1. 将堆顶元素对堆中最后一个元素交换2. 将堆中有效数据个数减少一个3. 对堆顶元素进行向下调整//删除元素 public int poll(){ int valelem[0]; int tmpelem[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对象否则会抛出NullPointerException4. 没有容量限制可以插入任意多个元素其内部可以自动扩容5. 插入和删除元素的时间复杂度为OlogN6. PriorityQueue底层使用了堆数据结构7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素4.2优先级队列的构造注意默认情况下PriorityQueue队列是小堆如果需要大堆需要用户提供比较器class IntCmp implements ComparatorInteger{ public int compare(Integer o1, Integer o2) { return o2-o1; } } public class TestPriorityQueue { public static void main(String[] args) { PriorityQueueInteger 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 ComparatorInteger{ public int compare(Integer o1,Integer o2){ return o2.compareTo(o1);//改为大根堆 } } class Solution { public int[] smallestK(int[] arr, int k) { int[] retnew int[k]; if(arrnull||k0){//对arr和k进行基本判断 return ret; } PriorityQueueInteger priorityQueuenew PriorityQueue(k,new Intcmp());//创建优先队列 for(int i0;ik;i){//将前k个元素放入堆 priorityQueue.offer(arr[i]); } for(int ik;iarr.length;i){//遍历剩余元素 int peekValpriorityQueue.peek(); if(arr[i]peekVal){//当前元素和堆顶元素比较小值放堆顶 priorityQueue.poll(); priorityQueue.offer(arr[i]); } } for(int i0;ik;i){ ret[i]priorityQueue.poll();//取出剩余堆元素 } return ret; } }五总结依旧小结整体来说堆这一节难度不大但是还是搞了挺久的可能冬天到了要冬眠了吧天天晕晕的。老己不要对自己太好哇如果方便的话请给作者点个赞吧如文章不全或有问题可私信我哦