wordpress the_excerpt();,东莞网站优化方式,绥化网站开发公司,泰安人才1、概念 队列#xff1a;是一种FIFO#xff08;First-In-First-Out#xff09;先进先出的数据结构#xff0c;对应于生活中的排队的场景#xff0c;
排在前面的人总是先通过#xff0c;依次进行。 优先队列#xff1a;是特殊的队列#xff0c;从“优先”一词#xff…1、概念 队列是一种FIFOFirst-In-First-Out先进先出的数据结构对应于生活中的排队的场景
排在前面的人总是先通过依次进行。 优先队列是特殊的队列从“优先”一词可看出有“插队现象”优先即比较大小。比如送
进医院的患者即便是按顺序到达的生病更加严重的往往优先级也会更高。优先队列至少含有两
种操作的数据结构
insert插入即将元素插入到优先队列中入队以及deleteMin删除最小者它的作用是找出、删除优先队列中的最小的元素出队。
PriorityQueue JDK1.8 中的 PriorityQueue底层使用了堆这种数据结构 而堆实际就是在完全二叉树的基础
上进行了一些调整。
2、堆 堆严格意义上来说又叫二叉堆Binary Heap因为它的结构是一颗完全二叉树堆一般分
为最大堆和最小堆。
堆的性质
堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树。
堆的分类
大根堆父亲节点的值大于孩子节点的值小根堆父亲节点的值小于孩子节点的值
数组表示堆 由于是完全二叉树节点的索引之间有着一定的关系故我们可以使用数组来存储二叉堆具体如下 如果从索引为0开始存储则父亲和孩子节点的索引关系如下
3、PriorityQueue
构造方法
构造方法说明PriorityQueue()不带参数默认容量为11PriorityQueue(int initialCapacity)参数为初始容量该初始容量不能小于1PriorityQueue(Collection? extends E c)参数为一个集合
常用方法
方法说明boolean offer(E e)插入元素e返回是否插入成功e为null会抛异常E peek()获取堆后面介绍堆顶元素如果队列为空返回nullE poll()删除堆顶元素并返回如果队列为空返回nullint size()获取有效元素个数void clear()清空队列boolean isEmpty()判断队列是否为空
注意
add方法等同offer。
4、Top-k问题 即求数据中前k个最大或者最小元素一般情况下数据量都会比较大。如果数据量大使用排序那种方法就不可取了那么如何解决呢
使用数据中前k个数据建堆 求前k个最大建小堆求前k个最小建大堆 用剩余的元素依次与堆顶元素比较 求前k个最大若比堆顶元素大则替换小堆堆顶元素求前k个最小若比堆顶元素小则替换大堆堆顶元素
代码示例
问题从文件中获取前10名的学生。
学生类
package com.ybw.interview.file.simple;import lombok.AllArgsConstructor;
import lombok.Getter;/*** 学生类** author weixiansheng* version V1.0* className Student* date 2023/11/28**/
AllArgsConstructor
Getter
public class Student {/*** 姓名** author: weixiansheng* date: 2023/11/28**/private String name;/*** 成绩** author: weixiansheng* date: 2023/11/28**/private Integer score;
}获取top k数据
package com.ybw.interview.file.simple;import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;import java.util.*;/*** 获取前10名学生** author weixiansheng* version V1.0* className TopStudents* date 2023/11/28**/
Slf4j
public class TopStudents {public static final int TEN 10;private MapString, Integer studentMap new HashMap();/*** 初始化数据** className TopStudents* author weixiansheng* date 2023/11/28* version V1.0**/BeforeEachpublic void init() {Random random new Random();for (int i 0; i 100; i) {studentMap.put(学生 i, random.nextInt(100));}}/*** 打印前10名学生** className TopStudents* author weixiansheng* date 2023/11/28* version V1.0**/Testpublic void printTopStudents() {//1、创建小顶堆PriorityQueueStudent topStudents new PriorityQueue(10, Comparator.comparingInt(Student::getScore));//2、构建前10名学生buildTopStudents(topStudents);//3、打印前10名学生for (int i 0; i TEN; i) {Student student topStudents.poll();log.info({}:{}, student.getName(), student.getScore());}}/*** 构建前10名学生** param topStudents* methodName: buildTopStudents* return: void* author: weixiansheng* date: 2023/11/28**/private void buildTopStudents(PriorityQueueStudent topStudents) {studentMap.forEach((name, score) - {if (topStudents.size() TEN) {topStudents.add(new Student(name, score));} else if (score topStudents.peek().getScore()) {topStudents.poll();topStudents.add(new Student(name, score));}});}
}打印日志
[INFO ] 2023-11-28 15:41:44.519 [main] c.y.i.file.simple.TopStudents - 学生59:92
[INFO ] 2023-11-28 15:41:44.520 [main] c.y.i.file.simple.TopStudents - 学生46:92
[INFO ] 2023-11-28 15:41:44.521 [main] c.y.i.file.simple.TopStudents - 学生28:93
[INFO ] 2023-11-28 15:41:44.521 [main] c.y.i.file.simple.TopStudents - 学生80:94
[INFO ] 2023-11-28 15:41:44.521 [main] c.y.i.file.simple.TopStudents - 学生21:94
[INFO ] 2023-11-28 15:41:44.521 [main] c.y.i.file.simple.TopStudents - 学生71:95
[INFO ] 2023-11-28 15:41:44.521 [main] c.y.i.file.simple.TopStudents - 学生75:95
[INFO ] 2023-11-28 15:41:44.521 [main] c.y.i.file.simple.TopStudents - 学生87:95
[INFO ] 2023-11-28 15:41:44.521 [main] c.y.i.file.simple.TopStudents - 学生82:97
[INFO ] 2023-11-28 15:41:44.521 [main] c.y.i.file.simple.TopStudents - 学生76:98参考文章
Java数据结构之优先级队列(PriorityQueue)用法详解_java_脚本之家
优先队列(PriorityQueue) - 简书
