赞
踩
队列:是一种FIFO(First-In-First-Out)先进先出的数据结构,对应于生活中的排队的场景,
排在前面的人总是先通过,依次进行。
优先队列:是特殊的队列,从“优先”一词,可看出有“插队现象”(优先即比较大小)。比如送
进医院的患者,即便是按顺序到达的,生病更加严重的往往优先级也会更高。优先队列至少含有两
种操作的数据结构:
JDK1.8 中的 PriorityQueue底层使用了堆这种数据结构 ,而堆实际就是在完全二叉树的基础
上进行了一些调整。
堆严格意义上来说又叫二叉堆(Binary Heap),因为它的结构是一颗完全二叉树,堆一般分
为最大堆和最小堆。
大根堆 | 父亲节点的值大于孩子节点的值 |
小根堆 | 父亲节点的值小于孩子节点的值 |
由于是完全二叉树,节点的索引之间有着一定的关系,故我们可以使用数组来存储二叉堆,具体如下:
如果从索引为0开始存储,则父亲和孩子节点的索引关系如下:
构造方法 | 说明 |
PriorityQueue() | 不带参数,默认容量为11 |
PriorityQueue(int initialCapacity) | 参数为初始容量,该初始容量不能小于1 |
PriorityQueue(Collection<? extends E> c) | 参数为一个集合 |
方法 | 说明 |
boolean offer(E e) | 插入元素e,返回是否插入成功,e为null,会抛异常 |
E peek() | 获取堆(后面介绍堆)顶元素,如果队列为空,返回null |
E poll() | 删除堆顶元素并返回,如果队列为空,返回null |
int size() | 获取有效元素个数 |
void clear() | 清空队列 |
boolean isEmpty() | 判断队列是否为空 |
注意:
即求数据中前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;
- }
- 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 Map<String, Integer> studentMap = new HashMap<>();
-
- /**
- * 初始化数据
- *
- * @className TopStudents
- * @author weixiansheng
- * @date 2023/11/28
- * @version V1.0
- **/
- @BeforeEach
- public 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
- **/
- @Test
- public void printTopStudents() {
- //1、创建小顶堆
- PriorityQueue<Student> 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(PriorityQueue<Student> 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
参考文章:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。