堆排序是一种高效的排序算法,基于二叉堆这一数据结构。二叉堆可以是最大堆或最小堆,堆排序利用了最大堆的特性来实现排序。
堆结构如下图,堆的实际结构是数组,但是我们在分析它的时候用的是有特殊标准的完全二叉树来分析。也就是说数组是堆的实际物理结构而完全二叉树是我们便于分析的逻辑结构。堆有两种:大根堆和小根堆。每个节点的值都大于其左孩子和右孩子节点的值,称为大根堆。每个节点的值都小于其左孩子和右孩子节点的值,称为小根堆。2. 交换并缩小堆:交换堆顶元素(最大值)和最后一个元素,然后缩小堆的范围,排除已排序的元素。3. 重新调整堆:重新调整剩余元素构成的堆,以保持最大堆的性质。4. 重复过程:重复步骤2和3,直到堆的大小减少到1,完成排序。一个算法题:从1000万个整数中选出100个最大的数。创建一个固定大小的线程池,初始化一个大小为100的PriorityQueue,使用自定义的比较器来实现最小堆(队列头部元素是最小的元素)。这个队列将用来存储最大的100个元素。由于我们希望找到最大的元素,所以比较器应该按照降序排列。
程序生成1000万个随机数,这些数字可以看作是数据集。在实际应用中,这些数据可能来自文件、数据库或网络。
1. PriorityQueue是线程不安全的,由于多个线程将并发访问和修改优先队列,必须使用同步机制来避免数据竞争和一致性问题。通常,这可以通过使用synchronized关键字或ReentrantLock等显式锁来实现。2. 在每个线程的任务中,生成的随机数被传递到同步块中,在那里它被优先队列处理。如果优先队列的大小小于100,新生成的数字将直接添加到队列中。如果队列已经满了,并且新数字大于堆顶的元素(即最小的元素),则将堆顶元素移除,并将新数字添加到队列中。PriorityQueue 是 Java 中的一种基于二叉堆实现的优先队列数据结构,它能够保证每次取出的元素都是队列中权值最小的元素。PriorityQueue 的底层实现是一个数组,通过堆的性质来维护元素的顺序。在 PriorityQueue 中,元素的优先级可以通过元素自身的自然顺序或者通过构造时传入的比较器(Comparator)来决定 。当你向 PriorityQueue 中添加元素时,它会根据元素的优先级将其插入到合适的位置。当你从 PriorityQueue 中删除元素时,它会将优先级最高的元素出队。这个过程是通过调整堆来实现的,确保了插入和删除操作的时间复杂度为 O(log n)。1. add(E e) 或 offer(E e):将元素添加到队列中。2. poll() 或 remove():移除并返回队列头部的元素,即优先级最高的元素。3. peek() 或 element():返回队列头部的元素但不移除它。PriorityQueue 的构造方法允许你指定初始容量或者提供一个比较器来自定义元素的排序方式。如果没有提供比较器,那么元素必须实现 Comparable 接口,以便 PriorityQueue 可以根据元素的自然顺序进行排序 。在实际应用中,PriorityQueue 可以用于实现如 Dijkstra 算法、Prim 算法、Huffman 编码等算法,这些算法都需要根据元素的优先级来进行操作。
吴灿锦,泰伯一百零一世孙,明朝开国名将安陆侯吴复的后代,吉林财经大学2019级本科生;
第九届中国国际“互联网+”创新创业大赛吉林省赛区金奖项目总负责人;
第十三届“挑战杯”中国大学生创业计划大赛吉林省赛区特等奖,国家级铜奖项目总负责人;
2022年荣获吉林财经大学创业实践国家级立项第一名项目总负责人。