堆排序算法实践——从1000万数据中找出最大的100项

文摘   职场   2024-08-10 22:50   广东  


序  言

摘要


第 1 章:堆排序介绍


第 2 章:堆排序算法实践


第 3 章:作者介绍



第 1 章

堆排序介绍


1.1、堆排序介绍


堆排序是一种高效的排序算法,基于二叉堆这一数据结构。二叉堆可以是最大堆或最小堆,堆排序利用了最大堆的特性来实现排序。

堆结构如下图,堆的实际结构是数组,但是我们在分析它的时候用的是有特殊标准的完全二叉树来分析。也就是说数组是堆的实际物理结构而完全二叉树是我们便于分析的逻辑结构。

堆有两种:大根堆和小根堆。每个节点的值都大于其左孩子和右孩子节点的值,称为大根堆。每个节点的值都小于其左孩子和右孩子节点的值,称为小根堆


1.2、堆排序步骤

1. 构建最大堆:将给定数组转换成最大堆。
2. 交换并缩小堆:交换堆顶元素(最大值)和最后一个元素,然后缩小堆的范围,排除已排序的元素。
3. 重新调整堆:重新调整剩余元素构成的堆,以保持最大堆的性质。
4. 重复过程:重复步骤2和3,直到堆的大小减少到1,完成排序。


第 2 章

堆排序实践


2.1、需求描述


一个算法题:从1000万个整数中选出100个最大的数。

2.2、思路分析


2.2.1、初始化

创建一个固定大小的线程池,初始化一个大小为100的PriorityQueue,使用自定义的比较器来实现最小堆(队列头部元素是最小的元素)。这个队列将用来存储最大的100个元素。由于我们希望找到最大的元素,所以比较器应该按照降序排列

2.2.2、数据生成

程序生成1000万个随机数,这些数字可以看作是数据集。在实际应用中,这些数据可能来自文件、数据库或网络

2.2.3、线程同步

1. PriorityQueue是线程不安全的由于多个线程将并发访问和修改优先队列,必须使用同步机制来避免数据竞争和一致性问题。通常,这可以通过使用synchronized关键字或ReentrantLock等显式锁来实现。

2. 在每个线程的任务中,生成的随机数被传递到同步块中,在那里它被优先队列处理。如果优先队列的大小小于100,新生成的数字将直接添加到队列中。如果队列已经满了,并且新数字大于堆顶的元素(即最小的元素),则将堆顶元素移除,并将新数字添加到队列中

2.3、PriorityQueue


2.3.1、PriorityQueue介绍

PriorityQueue 是 Java 中的一种基于二叉堆实现的优先队列数据结构,它能够保证每次取出的元素都是队列中权值最小的元素

PriorityQueue 的底层实现是一个数组,通过堆的性质来维护元素的顺序。在 PriorityQueue 中,元素的优先级可以通过元素自身的自然顺序或者通过构造时传入的比较器(Comparator)来决定  。

当你向 PriorityQueue 中添加元素时,它会根据元素的优先级将其插入到合适的位置。当你从 PriorityQueue 中删除元素时,它会将优先级最高的元素出队。这个过程是通过调整堆来实现的,确保了插入和删除操作的时间复杂度为 O(log n)

2.3.2、PriorityQueue常用API

1. add(E e) 或 offer(E e):将元素添加到队列中。
2. poll() 或 remove():移除并返回队列头部的元素,即优先级最高的元素。
3. peek() 或 element():返回队列头部的元素但不移除它。
4. size():返回队列中的元素数量。
5. clear():移除队列中的所有元素。

2.3.3、PriorityQueue应用场景

PriorityQueue 的构造方法允许你指定初始容量或者提供一个比较器来自定义元素的排序方式。如果没有提供比较器,那么元素必须实现 Comparable 接口,以便 PriorityQueue 可以根据元素的自然顺序进行排序 。

在实际应用中,PriorityQueue 可以用于实现如 Dijkstra 算法、Prim 算法、Huffman 编码等算法,这些算法都需要根据元素的优先级来进行操作。

2.4、代码实现




第 3 章

作者介绍


吴灿锦,泰伯一百零一世孙,明朝开国名将安陆侯吴复的后代,吉林财经大学2019级本科生;


第九届中国国际“互联网+”创新创业大赛吉林省赛区金奖项目总负责人;


第十三届“挑战杯”中国大学生创业计划大赛吉林省赛区特等奖,国家级铜奖项目总负责人;


2022年荣获吉林财经大学创业实践国家级立项第一名项目总负责人。


· 往期回顾 ·


“互联网+”金奖与“挑战杯”特等奖——青春的舞台,美好的回忆
《刻意练习》深度解读——如何通过刻意练习让你变成一个卓越的人
数据结构与算法——从入门到精通全攻略
统一身份管理系统的权限设计方案与实践探索
Vue3前端框架实战手册——从入门到精通全攻略
ElasticSearch分布式搜索引擎实战手册——从入门到精通全攻略
Vue前端框架实战手册——从入门到精通全攻略
大数据高并发系统架构实战方案
SpringCloud微服务架构实战手册——从入门到精通全攻略
优秀毕业设计示例——基于SpringCloud Alibaba微服务在线教育系统的设计与实现的路演答辩
RabbitMQ异步通信全攻略——API操作与性能调优实战
Redis核心API速览与实战应用手册
JDK核心API速查手册与实用指南
Java开发手册阅读心得——黄山版
SpringBoot项目常用注解的积累与代码的优化实践
Spring Framework——掌握核心注解,优化你的应用程序
工作中常用的Linux命令——以阿里云ECS服务器为例
Mysql数据库系统学习笔记


远方的音讯
梧桐长成凤凰至,人伴贤良品行高!
 最新文章