目录

1.优先级队列

2. 堆的概念

3. 堆的存储方式

4. 堆的创建

4.1 向下调整

4.2 堆的创建

4.3 堆的插入

4.4 堆的删除

5.用堆模拟实现优先级队列

6.常用接口的介绍

6.1 PriorityQueue 的特性

6.2 PriorityQueue 的方法

7. Top K问题


1.优先级队列

队列是一种先进先出的数据结构,这种数据类型每次元素的入队和出队都只能分别在队尾和队头进行,但在一些情况,人们并不需要队列的第一个元素,需要操作的数据可能带有优先级,所以在出队的时候,可能需要优先级更高的元素先出队列。比如外卖派单系统,平台需要快速分配最近的订单,此时需要根据距离的远近优先分配,这个时候优先级就是距离。

优先级队列,它并不是队列队列,不满足先进先出的条件,可以把它理解为一个堆,堆顶元素就是放优先级更高的元素,在加入元素时,堆的状态也要根据新加元素来判断调整优先级元素,而不是单单的指队列的队头或者队尾元素 。所以,优先级队列满足两个基本操作,一是返回最高优先级对象,二是添加新的对象。

2. 堆的概念

如果一个关键码的集合 K = {k0, k1, k2, k3, ..., kn - 1},把它的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中,并满足 Ki <= K2i + 1 且 Ki <= K2i + 2(或:Ki >= K2i + 1 且 Ki >= K2i + 2) ,称为小堆(或:大堆)根节点是所有节点最小的堆叫做最小堆或小根堆,根节点是所有节点最大的堆叫做最大堆或大根堆

堆的性质:

  • 堆的一棵完全二叉树
  • 堆中的节点的值一定不大于或不小于其父亲节点的值

3. 堆的存储方式

堆是一棵完全二叉树,所有可以采用层序遍历的方式进行高效存储。

对于普通的二叉树,并不适用顺序方式进行存储,为了更好地还原二叉树,空间就需要存储二叉树的空节点,这样会导致空间利用率降低。

如果定义根节点的下标从 0 开始,即 i 是数组的下标,那么对于任一节点 i ,它的双亲节点下标是 ( i - 1 ) / 2 ( i != 0),左孩子节点下标是 2 * i + 1 ( 2 * i + 1 < 节点个数),右孩子节点下标是 2 * i + 2 ( 2 * i + 2 < 节点个数)。

4. 堆的创建

4.1 向下调整

对于给定一个集合{1,20,15,18,16,12,13,8,9},怎么把它建成一个大根堆呢?

观察可以发现,这个数组集合除了根节点外,其余节点已经基本满足大根堆的条件,这个时候只需要把根节点向下调整。

步骤(这里是建大根堆):

假设根节点设为 parent 用来标记需要调整的节点,child 标记根节点的左孩子(根据完全二叉树可以知道如果根节点存在孩子节点,那么一定拥有左孩子),孩子节点 child 不能大于数组长度,即 child < size,则有:

  1. 如果 parent 的左孩子存在,并且判断是否存在右孩子,如果没有右孩子,则 parent 和左孩子节点比较,如果 parent < child进行交换,否则不交换;如果有右孩子,左孩子和右孩子作比较,找到它们的最大值,然后再比较孩子节点和双亲节点的大小,如果满足双亲结点小于孩子节点,进行交换,否则不交换;
  2. 不论是否交换,比较过后,双亲节点 parent 都要指向较小的值,然后继续向下调整,即 parent = child,child = 2 * parent + 1;
  3. 重复上述步骤,知道调整比较到最后一个叶子节点位置

这种比较是次数是根据二叉树的高度来确定,所有它的时间复杂度是0(log N)。

4.2 堆的创建

上述例子是在基本有序的情况下,只需要小幅度调整就可以完成。那么对于普通的序列{1,9,8,12,16,13,15,20,17},怎么才能把它创建成一个大根堆呢?

对这个序列初始化堆如下:

要解决这个问题,就要找到最后一个非叶子节点的下标,最后一个非叶子节点也就是最后一个叶子节点的的双亲结点,然后和它的左右孩子作比较,如果双亲结点小于孩子节点,就做交换,交换后检查被交换的子树,如果被交换的子树结构被破坏,需要递归下沉调整,最后再找上一个非叶子节点,重复上述步骤,直到调整到根节点为止。

代码:

public class Heap {public int[] elem;public int usedSize;//堆的元素个数public Heap() {this.elem = new int[10];//初始化数组大小}//创建堆public void createHeap(int[] array) {for (int i = 0; i < array.length; i++) {elem[i] = array[i];usedSize++;}//usedSize - 1 是最后一个节点的下标,for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {shiftDown(parent , usedSize);}}//交换public void swap(int[] elem , int i , int j) {int tmp = elem[i];elem[i] = elem[j];elem[j] = tmp;}//向下调整private void shiftDown(int parent,int usedSize) {int child = 2 * parent + 1;//标记左孩子的位置while (child < usedSize) {//if里面的条件不能交换,比较先判断右孩子节点是否存在if (child + 1 < usedSize && elem[child] < elem[child + 1]) {//如果有右孩子并且右孩子大于左孩子,更改孩子的位置child++;}if (elem[parent] < elem[child]) {//如果双亲节点小于孩子节点,交换swap(elem , child , parent);//交换后更新双亲结点和孩子节点parent = child;child = 2 * parent + 1;} else {//如果双亲结点大于孩子节点,不需要做交换break;}}}
}

4.3 堆的插入

如果要在下面这棵树插入一个 25 的节点的节点,应该怎么操作呢?

上面的二叉树,根据层序遍历的结果就是 20,18,15,9,16,12,13,8,1,其底层是数组实现的,要插入元素是25,观察 25 比任何元素都大,那是不是把所有的元素后移一位,任何 25 插入到第一个位置就行呢?也就是:

如果这么操作之后,那么这个堆就不再是大根堆了,很明显不符合。可以换一个角度思考,既然堆是完全二叉树,那么新插入的元素就紧接着最后应该元素追加就好了(也就是堆的末尾),然后把这个新加入的节点和它的双亲节点作对比,如果比双亲节点大,那么就进行交换,然后更新这个新加入节点的下标,直到和根节点左比较为止

所以,堆的插入应该要满足:

  1. 把新加的元素放入堆的末尾,虽然堆的本质是二叉树,但是它是根据数组来实现的,所以在末尾追加时先判断数组是否已满
  2. 将新加的元素节点进行向上调整,直到满足堆的性质

代码:

    //新增元素后也要满足大根堆public void offer(int val) {if (isFull()) {//如果满,扩容this.elem = Arrays.copyOf(elem , 2 * elem.length);}elem[usedSize] = val;//在末尾追加shiftUp(usedSize);//调用向上调整usedSize++;//元素个数加1}//向上调整,新增的元素位置为孩子节点private void shiftUp(int child) {int parent = (child - 1) / 2;//找到双亲节点while (parent >= 0) {if (elem[parent] < elem[child]) {//孩子节点大于双亲节点,进行交换swap(elem , child , parent);child = parent;parent = (child - 1) / 2;} else {//如果孩子节点不大于双亲节点,则说明新加的元素在末尾追加时,就已经满足大根堆的性质break;}}}//判满public boolean isFull() {return usedSize == elem.length;}

4.4 堆的删除

堆的删除,删除的是堆顶元素,这也正是设计堆的原因,希望在第一个元素就可以找到优先级更高的元素。查看元素时,查看的也是堆顶元素。如何实现呢?

堆的删除并不能说像链表一样删除头节点,改变头节点的指向,在这里也就是后面的元素依次往前挪,这样是不行的,因为也会破坏堆的结构。其实可以先想一下删除后的结果:堆的元素个数一定会减 1 ,那么只需要把原本的堆中最后一个元素的位置和堆顶元素的位置交换一下,此时对交换后的堆顶元素发生向下调整,就可以完成操作。

代码:

    //删除元素,删除之后也要满足大根堆public int poll() {checkEmpty();//判断是否为空int val = elem[0];swap(elem , 0 , usedSize-1);shiftDown(0 , usedSize-1 );usedSize--;return val;}public boolean isEmpty() {return usedSize == 0;}//判断是否为空,如果空就没有元素可以删public void checkEmpty() throws EmptyException{if (isEmpty()) {throw new EmptyException("数组为空!!!");}}//查看堆顶元素public int peek() {checkEmpty();return elem[0];}

5.用堆模拟实现优先级队列

实现优先级队列,其实就是创建堆的过程。

6.常用接口的介绍

6.1 PriorityQueue 的特性

Java集合框架提供了 PriorityQueue 和 PriorityBlockingQueue 两种类型的优先级队列, PriorityQueue 是线程不安全的, PriorityBlockingQueue 是线程安全的。在这里主要了解  PriorityQueue。

注意事项:

1. PriorityQueue 中的元素是需要可以比较大小的,如果插入的对象不能比较大小,就会抛出 ClassCastException 异常

2. 不能插入 null 对象,否则会抛出 NullPointerException

3. 没有容量限制,可以插入任意多个元素,其内部自动扩容(源码如下)并且从源码中可以看出,在优先级队列中,如果容量小于 64 时,扩容是 2 倍扩容,如果容量大于 64 时,按照 1.5 倍扩容

4. 插入和删除的时间复杂度都是O(log N)

5. PriorityQueue 底层是的数据结构是堆,并且默认情况下是最小堆/小根堆,即堆顶元素是最小的元素

6.2 PriorityQueue 的方法

构造方法:

常用方法:

7. Top K问题

Top K问题通常指从一个数据集中找出前 K 个最大(或最小)的元素,或出现频率最高(或最低)的 K 个元素

想要找到一组数据中前 K 个最大(或最小)的元素,或出现频率最高(或最低)的 K 个元素,一种非常暴力的解法就是对这组数组进行排序,然后找到前 K 个元素即可,但是如果数据量非常大的时候,想要把所有数据一下子全部加载到内存的时候,可能无法实现。这时候就可以用堆的方式来解决。但还要一个问题,既然建立堆,那是把所有的数据都建立成堆吗?如果数据非常庞大,那肯定也建立不起来,所以最好的方法就是把这组数据的前 K 个元素建立成堆,然后遍历剩下的 N - K 个元素和堆顶元素作比较,是要较大值还是较小值,根据需求而定。

已经知道了用堆可以解决这类问题,但是在解决之前还有一个问题要解决。就是堆是用来排序的,有大根堆和小根堆,如果要找前 K 个最小的元素,是建立大根堆还是小根堆呢?仔细想想堆的性质,如果是建立小根堆,那么堆顶元素永远是最小值,建立小根堆的目的是堆顶元素就是优先级较高的元素,想要求前 K 个最小的元素,但是当一个剩下的 N- K 个元素和堆顶做比较时,可能比堆顶元素大,但是否比除了堆顶元素之外的元素小,这个情况是没办法判断的,因为堆只能瞄到堆顶元素。所以如果要找前 K 个最小的元素,应该建立大根堆

建立大堆后,遍历剩下的 N - K个元素和堆顶元素作比较,如果比堆顶元素还小,遍历到符合条件的元素加入,把堆顶元素删除,直到遍历整组数据结束。 

总结:

求前 K 个最大元素,建立小根堆

求前 K 个最小元素,建立大根堆

最小 K 个数 :

代码(求前K个最小元素):

//自定义实现一个比较接口类,因为PriorityQueue默认是升序,即建立的是小根堆,与题意要求相反,所以需要重新定义比较接口
class IntCom implements Comparator<Integer> {@Overridepublic int compare(Integer o1 , Integer o2) {return o2.compareTo(o1);}
}
public class Main {public static int[] smallestK(int[] arr, int k) {int[] ret = new int[k];if(arr == null || k == 0){return ret;}//方法:建立一个大小为K的大根堆,然后遍历N-K个元素,PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k , new IntCom());//调用比较方式//把前K个元素建立大根堆for (int i = 0; i < k; i++) {priorityQueue.offer(arr[i]);}//遍历剩下的N - K个元素for (int i = k; i < arr.length; i++) {int peekVal = priorityQueue.peek();//看堆顶元素的值if (arr[i] < peekVal) {//如果遍历的元素小于堆顶元素,堆顶元素删除,新元素加入priorityQueue.poll();priorityQueue.offer(arr[i]);}}//走到这里,说明现在的堆中所有元素就是需要的前K个最小元素//堆新堆进行遍历,因为要返回前K个最小的元素for (int i = 0; i < k; i++) {ret[i] = priorityQueue.poll();}Arrays.sort(ret);return ret;}public static void main(String[] args) {int[] array = {1 , 9 , 15 , 36 , 66 , 88 , 99 , 42 , 8 , 7};int[] ret = smallestK(array , 3);for (int num : ret) {System.out.print(num + " ");}}
}

输出结果:


(感谢阅读,文章较长,如有错误,还望指正!撒花❀❀❀

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/diannao/95055.shtml
繁体地址,请注明出处:http://hk.pswp.cn/diannao/95055.shtml
英文地址,请注明出处:http://en.pswp.cn/diannao/95055.shtml

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C语言自定义类型深度解析:联合体与枚举

在C语言中&#xff0c;自定义类型为数据组织提供了极大的灵活性。除了常用的结构体&#xff0c;联合体&#xff08;共用体&#xff09;和枚举也是非常重要的自定义类型。本文将结合实例&#xff0c;详细解析联合体和枚举的特性、用法及实际应用场景。 一、联合体&#xff08;Un…

Numpy科学计算与数据分析:Numpy数据分析基础之统计函数应用

Numpy统计函数实战&#xff1a;数据的聚合与分析 学习目标 通过本课程的学习&#xff0c;学员将掌握Numpy中用于统计分析的关键函数&#xff0c;如求和(sum)、平均值(mean)、标准差(std)等&#xff0c;能够熟练地在实际数据集中应用这些函数进行数据的聚合与分析。 相关知识…

从引导加载程序到sysfs:Linux设备树的完整解析与驱动绑定机制

摘要本报告旨在为嵌入式Linux开发者详细梳理设备树&#xff08;Device Tree, DT&#xff09;在系统启动中的完整解析流程。报告将从引导加载程序&#xff08;Bootloader&#xff09;如何准备和传递设备树二进制文件&#xff08;DTB&#xff09;开始&#xff0c;逐步深入到内核如…

基于深度学习的污水新冠RNA测序数据分析系统

基于深度学习的污水新冠RNA测序数据分析系统 摘要 本文介绍了一个完整的基于深度学习技术的污水新冠RNA测序数据分析系统&#xff0c;该系统能够从未经处理的污水样本中识别新冠病毒变种、监测病毒动态变化并构建传播网络。我们详细阐述了数据处理流程、深度学习模型架构、训练…

宝塔面板配置Nacos集群

一、环境准备 准备三台及以上的服务器&#xff0c;我这里准备了3台服务器&#xff0c;172.31.5.123&#xff5e;125&#xff1b;分别安装好宝塔面板&#xff0c;软件商店里安装nacos&#xff1b;二、Nacos集群配置 配置数据库连接&#xff1a;​ 进入每台服务器上 Nacos 解压后…

Spring Boot 3.x 全新特性解析

Spring Boot 是企业级 Java 开发中最常用的框架之一。自 Spring Boot 3.x 发布以来&#xff0c;其引入的一系列重大变更与优化&#xff0c;为开发者提供了更现代、更高效的开发体验。本文将重点解析 Spring Boot 3.x 的关键特性及其对项目架构的影响。 一、基于 Jakarta EE 10 …

2025.8.10总结

今天晚上去跑了2公里&#xff0c;跑完还挺爽的&#xff0c;然后花了1.5个小时去公司刷题&#xff0c;没有进行限时练&#xff0c;花了一周的时间才做完这题&#xff0c;共找了20个bug&#xff0c;虽然没有进行限时练&#xff0c;但我仿佛对测试技术掌握得更好了&#xff0c;知道…

qt中实现QListWidget列表

使用最基本的QListWidgetItem来创建列表项&#xff0c;具体使用下面setText、setIcon、addItem这三个方法#include "mainwindow.h" #include "ui_mainwindow.h" #include "QDebug"enum CustomRoles {IdRole Qt::UserRole, // 存储IDPhoneR…

nginx-主配置文件

nginx-主配置文件一、主配置文件nginx.conf内容二、修改配置的文件后的操作三、配置虚拟主机的域名1. 修改nignx.conf配置文件2. 新建域名对应的网页根目录3. 重载nginx配置4. 验证一、主配置文件nginx.conf内容 [rootweb1 conf]# cat nginx.conf#user nobody; # nginx woke…

DBSACN算法的一些应用

以下是 DBSCAN 算法在 Python 中的几个典型应用示例&#xff0c;涵盖了基础使用、参数调优和可视化等方面&#xff1a;import numpy as np import matplotlib.pyplot as plt from sklearn.cluster import DBSCAN from sklearn.datasets import make_moons, make_blobs from skl…

java9学习笔记-part1

G1 成为默认垃圾回收器在 Java 8 的时候&#xff0c;默认垃圾回收器是 Parallel Scavenge&#xff08;新生代&#xff09;Parallel Old&#xff08;老年代&#xff09;。到了 Java 9, CMS 垃圾回收器被废弃了&#xff0c;G1&#xff08;Garbage-First Garbage Collector&#x…

【github.io静态网页 怎么使用 github.io 搭建一个简单的网页?】

这里是一张展示 GitHub Pages 静态网站架构与部署流程的示意图&#xff0c;可以帮助你更直观理解整个流程。 要使用 github.io&#xff08;GitHub Pages&#xff09;搭建一个简单的网页&#xff0c;你可以按照以下步骤操作&#xff1a; 快速入门&#xff1a;个人网站&#xff…

记录一次ubuntu20.04 解决gmock not found问题的过程

在电脑上源码编译moveit&#xff0c;系统是ubuntu20.04&#xff0c;有三个电脑&#xff0c;分别叫做A,B,C好了&#xff0c;A和C都可以很顺畅地走流程编译通过&#xff0c;但是B遇到了gmock not found的问题&#xff0c;一开始没当回事&#xff0c;感觉重装下库&#xff0c;或者…

Java基础编程核心案例:从逻辑到应用

Java编程的核心在于将逻辑思维转化为可执行的代码。本专栏通过8个实用案例&#xff0c;覆盖条件判断、循环结构、数组操作、用户交互等基础知识点&#xff0c;展示如何用Java解决实际问题&#xff0c;从简单游戏到数据计算&#xff0c;逐步构建编程思维。 案例一&#xff1a;剪…

Starlink卫星终端对星策略是终端自主执行的还是网管中心调度的?

以下文章首先来源于Google Gemini的Deep Research的内容,在Deep Research的报告参考了SpaceX公开信息、FCC技术报告、相关专利(如US9906292B2)以及学术研究的综合分析,并参考了RFWirelessWorld和APNIC博客等二次来源。 文章完成之后,前后发给了Grok和deepseek,让Grok和d…

【CDA案例】数据分析案例拆解:解锁数据分析全流程!

在当今数字化时代&#xff0c;数据如同一座座金矿&#xff0c;蕴含着巨大的价值。企业、组织乃至个人都渴望从海量的数据中挖掘出有用的信息&#xff0c;以指导决策、优化运营、提升竞争力。今天我们以一个实际的数据分析案例为蓝本&#xff0c;深入拆解其全过程&#xff0c;带…

vulnhub-drippingblues靶场攻略

1.打开靶场&#xff0c;我们将网络连接方式改为NAT模式2.然后使用nmap扫描一下nat的网段3.存在21&#xff0c;22&#xff0c;80端口我们先来看一下21端口的ftp协议&#xff0c;发现可以直接匿名登录&#xff0c;并且可以下载存在的东西4.但是这个压缩包被加密了&#xff0c;我们…

afsim2.9_使用QtCreator和VSCode编译

使用QtCreator和VSCode编译AFSIM2.9源代码指南 准备工作 在开始编译AFSIM2.9源代码前&#xff0c;需要确保您的开发环境满足以下条件&#xff1a; 安装QtCreator安装Visual Studio Code&#xff08;最新稳定版&#xff09;获取AFSIM2.9源代码包安装必要的编译工具链&#xf…

TC39x STM(System Timer)学习记录

STM有哪些特性&#xff1f;自由运行的 64 位计数器所有 64 位可同步读取可同步读取 64 位计数器的不同 32 位部分基于与 STM 部分内容的比较匹配&#xff0c;灵活地产生服务请求在应用复位后自动开始计数若 ARSTDIS.STMxDIS 位清零&#xff0c;应用复位将复位 STM 寄存器&#…

css初学者第四天

<1>snipaste工具的使用snipaste是一个简单但强大的截图工具&#xff0c;也可以让你将截图贴回屏幕上。常用的快捷方式&#xff1a;1、F1可以截图&#xff0c;同时测量大小&#xff0c;设置箭头 书写文字等2、F3在桌面置顶显示3、点击图片&#xff0c;alt可以取色&#xf…