堆(堆排序,TOP K, 优先级队列)
1 概念解释
堆的定义:堆是一颗完全二叉树,分为大堆和小堆
大堆:一棵树中,任何父亲节点都大于等于孩子的节点,大堆的根结点最大
小堆:一棵树中,任何父亲节点都小于等于孩子节点,小堆的根节点最小
TOP K问题(元素个数远远大于K)
要求:从N个数中找出前K个最大的数(N >> K)
方法一: 假设是从100个数中找前10个最大的数,先用快速排序法对数据进行降序,前十个就是最大的,时间复杂度O(NlogN)
方法二: 将N个数依次push到大堆中,那么堆顶的元素肯定是最大的,然后pop K次,就找到了前K个最大的数,时间复杂度O(N+k*log2N后面会再次证明)。
那这是Topk问题吗?, 不完全是,
Topk问题的前提是: N非常大,若N为10亿、20亿,内存中无法存下这些数,只能存储在磁盘中,那上面的两种方式就不适用了
思路打开,可以先将前K个数建为小堆。
首先将前K个数建立成小堆, 然后将剩下N-K个数不断和堆顶比较,将大于堆顶的元素放入堆中,后然后向下调整后,最后堆中的K个数就是前K个最大的数。
时间复杂度为:K+(N-K)* logK 也就是O(NlogK)
注意:这里建立的是小堆而不是大堆。
因为如果是大堆,那么堆顶的数是堆中最大的,和剩下的N-K个数比较时,如果当前堆顶的数就是N个数中最大的,那么就把后面的数都挡在堆外了。这种只能找到N个数中最大的数。
总结:
TopK问题:通过建小堆,找到N个数中最大的前K个,建大堆,找到N个数中最小的前K个
堆排序:排升序建大堆,排降序建小堆
2 代码实现
建立堆的规则:
若下标从1开始时,其节点的计算为如下(树中第一个非叶子节点直接为len(最后一个节点的索引)/2)
若下标从0开始时,计算父节点,为**(当前索引 - 1) / 2**,左孩子:当前索引 × 2 +1;右孩子2: 当前索引 ×2 + 2
定义:
int parent(int root){return root / 2;
}
int left(int root){return root * 2;
}
int right(int root){return root * 2 + 1;
}
上浮:
//上浮public void swim(int low, int high){ //将[low...high]上浮为大顶堆,从high开始,由下往上int i = high, j = i / 2;while (j >= low){if (a[i] > a[j]){int temp = a[j];a[j] = a[i];a[i] = temp;i = j;j = i /2;}else {break;}}}
下沉:
//下沉public void sink(int low, int high){ //将[low...high]下沉为大顶堆,从low开始,由上往下int i = low, j = 2 * low;while (j <= high){if (j + 1 <= high && a[j] < a[j+1]){j++;}if (a[j] > a[i]){int temp = a[i];a[i] = a[j];a[j] = temp;i = j;j = 2 * i;}else {break;}}}
插入:
public void insert(int num){ //插入操作,插到堆的尾部,然后进行上浮size++;a[size] = num;swim(1,size);}
下沉:
public int delMax(){ //去除堆顶元素,删除堆的顶部元素,然后进行下沉int temp = a[1];a[1] = a[size];size--;sink(1,size);return temp;}
建堆(第一种是调用插入函数,从空开始建堆,是向上调整。第二种是提供现成的元素数组,从最后一个非叶子节点,向下调整)
static void TreeeAdjust(int a[], int low, int high){ //本质还是下沉操作,对low所指元素下沉int i = low, j = 2 * low + 1; //i表示父节点,j表示左孩子,下标从0开始 while(j <= high){if (j + 1 <= high && a[j] <= a[j+1]){ //j指向左右孩子较大的那个j++;}//开始下沉if(a[i] < a[j]){ //什么时候下沉,大顶堆-》当父节点小于子节点时;小顶堆-》当父节点大于子节点时下沉int temp = a[i];a[i] = a[j];a[j] = temp;i = j;j = 2 * i + 1;}else {break;}}}public static void bulidBigTree (int[] arr){ //构造大顶堆int len = arr.length-1;for (int i = len/2 - 1; i >= 0; i--){TreeeAdjust(arr, i, len);}}public static void sortBigTree(int[] arr){ //堆排序,交换元素以维持堆的定义。int len = arr.length;int i = len - 1;while (i >= 0){int temp = arr[i];arr[i] = arr[0];arr[0] = temp;i--;TreeeAdjust(arr, 0,i);}}
堆排序问题
升序:建大顶堆,然后交换堆顶和堆尾元素,重复调用下沉操作
降序:建大顶堆,然后交换堆顶和队尾元素,重复调用下沉操作(两次下沉结构一样,判断条件不同)
大堆:
static void TreeeAdjust(int a[], int low, int high){ //本质还是下沉操作int i = low, j = 2 * low + 1; //i表示父节点,j表示左孩子,下标从0开始while(j <= high){if (j + 1 <= high && a[j] <= a[j+1]){j++;}if(a[i] < a[j]){ //什么时候下沉,大顶堆-》当父节点小于子节点时;小顶堆-》当父节点大于子节点时下沉int temp = a[i];a[i] = a[j];a[j] = temp;i = j;j = 2 * i + 1;}else {break;}}}public static void bulidBigTree (int[] arr){ //构造大顶堆int len = arr.length-1;for (int i = len/2 - 1; i >= 0; i--){TreeeAdjust(arr, i, len);}}public static void sortBigTree(int[] arr){ //堆排序,交换元素以维持堆的定义。int len = arr.length;int i = len - 1;while (i >= 0){int temp = arr[i];arr[i] = arr[0];arr[0] = temp;i--;TreeeAdjust(arr, 0,i);}}
建立大堆和小堆关键的区别就在于下沉操作的判断条件
(将圈中的判断改成<就变成小堆)
大堆下沉: 当父节点小于子节点时(和较大的子节点交换位置)
小堆下沉:当父节点大于子节点时(和较小的子节点交换位置)
大堆上升:子节点大于父节点(直接判断)
小堆上升:当子节点小于父节点(直接判断)
每次分析时(按照这个最小的单位进行分析上浮和下沉)
3优先级队列
Java 优先队列 PriorityQueue
- Java 优先队列默认是小顶堆,小的先出队。
PriorityQueue<Integer> pq = new PriorityQueue<>()
建立大顶堆:
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->(b-a));
2.其他排序规则
//将pair按照key从大到小排序,key相同情况下,按照value从小到大排序。PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(n, new Comparator<Pair<Integer, Integer>>() {public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {if(o1.getKey() - o2.getKey() < 0) {return 1;} else if(o1.getKey() - o2.getKey() == 0){if(o1.getValue() - o2.getValue() < 0) {return -1;} else {return 1;}}return -1;}});
// 在数组情况下,pair的key为数组值,value为下标,
// 实现上述排序的一种巧妙做法。注:nums[] 为数组
PriorityQueue<Integer> pqMin = new PriorityQueue<>(new Comparator<Integer>() {public int compare(Integer o1, Integer o2) {if(nums[o1] - nums[o2] < 0) {return -1;} else if(nums[o1] - nums[o2] == 0){if(o1 - o2 < 0) {return -1;}}return 1;}});PriorityQueue<Integer> pqMax = new PriorityQueue<>(new Comparator<Integer>() {public int compare(Integer o1, Integer o2) {if(nums[o1] - nums[o2] > 0) {return -1;} else if(nums[o1] - nums[o2] == 0){if(o1 - o2 > 0) {return -1;}}return 1;}});//Lambda表达式PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->(b-a));
优先队列常用方法
public boolean add(E e); //在队尾插入元素,插入失败时抛出异常,并调整堆结构
public boolean offer(E e); //在队尾插入元素,插入失败时抛出false,并调整堆结构public E remove(); //获取队头元素并删除,并返回,失败时前者抛出异常,再调整堆结构
public E poll(); //获取队头元素并删除,并返回,失败时前者抛出null,再调整堆结构public E element(); //返回队头元素(不删除),失败时前者抛出异常
public E peek();//返回队头元素(不删除),失败时前者抛出nullpublic boolean isEmpty(); //判断队列是否为空
public int size(); //获取队列中元素个数
public void clear(); //清空队列
public boolean contains(Object o); //判断队列中是否包含指定元素(从队头到队尾遍历)
public Iterator<E> iterator(); //迭代器
插入元素 offer()方法,返回值boolean,再次调整堆结构
删除元素 poll()方法,返回堆顶元素,再次调整堆结构
获取堆头元素 peek()方法,返回堆顶元素
判断队列是否为空** isEmpty(); **
获取队列中元素个数**size(); **
判断队列中是否包含指定元素(从队头到队尾遍历)**contains(Object o); **
参考链接:
https://blog.csdn.net/weixin_46016019/article/details/123774875
相关文章:

堆(堆排序,TOP K, 优先级队列)
1 概念解释 堆的定义:堆是一颗完全二叉树,分为大堆和小堆 大堆:一棵树中,任何父亲节点都大于等于孩子的节点,大堆的根结点最大 小堆:一棵树中,任何父亲节点都小于等于孩子节点,小堆…...

(三)行为模式:11、模板模式(Template Pattern)(C++示例)
目录 1、模板模式含义 2、模板模式的UML图学习 3、模板模式的应用场景 4、模板模式的优缺点 5、C实现的实例 1、模板模式含义 模板模式(Template Method Pattern)是一种行为设计模式,它定义了一个操作中的算法骨架,将某些步骤…...
贝叶斯中的充分统计量
内容来源 贝叶斯统计(第二版)中国统计出版社 前两篇笔记简述经典统计中的充分统计量和判断充分统计量的 N e y m a n Neyman Neyman 因子分解定理 而在贝叶斯统计中,充分统计量也有一个充要条件 定理兼定义 设 x ( x 1 , x 2 , ⋯ , x …...

012:ArcGIS Server 10.2安装与站点创建教程
摘要:本文详细介绍地理信息系统服务器软件ArcGIS Server 10.2的安装与站点创建流程。 一、软件介绍 ArcGIS Server 10.2是Esri公司开发的一款强大的地理信息系统(GIS)服务器软件。它支持发布和共享地图、地理数据处理服务及空间分析功能&…...

xlive.dll错误的详细解决办法步骤教程,xlive.dll基本状况介绍
在计算机的众多文件中,“xlive.dll”扮演着独特而重要的角色。所以当你的电脑丢失了xlive.dll文件时,会倒是电脑不能正常运行,那么出现这样的问题有什么办法可以将丢失的xlive.dll进行修复呢?今天这篇文章将和大家聊聊xlive.dll错…...
通俗易懂的餐厅例子来讲解JVM
餐厅版本 JVM(Java虚拟机)可以想象成一个虚拟的计算机,它能够运行Java程序。为了让你更容易理解,我们可以用一个餐厅的比喻来解释JVM: 菜单(Java源代码): 想象一下,Java…...
Python从入门到高手7.3节-列表的常用操作方法
目录 7.3.1 列表常用操作方法 7.3.2 列表的添加 7.3.3 列表的查找 7.3.4 列表的修改 7.3.5 列表的删除 7.3.6 与列表有关的其它操作方法 7.3.7 与10月说再见 7.3.1 列表常用操作方法 列表类型是一种抽象数据类型,抽象数据类型定义了数据类型的操作方法。在本…...

Prompt提示词设计:如何让你的AI对话更智能?
Prompt设计:如何让你的AI对话更智能? 在人工智能的世界里,Prompt(提示词)就像是一把钥匙,能够解锁AI的潜力,让它更好地理解和响应你的需求。今天,我们就来聊聊如何通过精心设计的Pr…...

2024-10月的“冷饭热炒“--解读GUI Agent 之computer use?phone use?——多模态大语言模型的进阶之路
GUI Agent 之computer use?phone use?——多模态大语言模型的进阶之路 1.最新技术事件浅析三、思考和方案设计工具代码部分1.提示词2.工具类API定义,这里主要看computer tool就够了 总结 本文会总结概括这一应用的利弊,然后给出分析和工具代…...
Me 攒的GPT修改论文提示词
没有会员的GPT They demonstrated that QGAN exhibits an exponential advantage over classical methods when using data consisting of samples of measurements made on high-dimensional spaces. 作为related work 时态对吗? 有需要修改的吗?你可…...

关于在vue2中接受后端返回的二进制流并进行本地下载
后端接口返回: 前端需要在两个地方写代码: 1.封装接口处,responseType: blob 2.接收相应处 download() {if (this.selectionList.length 0) {this.$message.error("请选择要导出的数据!");} else {examineruleExport…...
[BUG]warn(f“Failed to load image Python extension: {e}“)的解决办法
在使用LlaMa-Factory工具包时,安装好环境后,输入llamafactory-cli env查看llama-factory的版本等信息时,bash提醒: /home/ubuntu/anaconda3/envs/Llama-Factory/lib/python3.10/site-packages/torchvision/io/image.py:13: UserW…...

配置MUX VLAN 的实验配置
概念和工作原理: MUX VLAN(Multiplex VLAN)是一种高级的VLAN技术,它通过在交换机上实现二层流量隔离和灵活的网络资源控制,提供了一种更为细致的网络管理方式。 概念与工作原理 基本概念: MUX VLAN通过定义主VLAN&am…...

高考相关 APP 案例分享
文章首发于https://qdgithub.com/article/2032 一、核心内容 (一)高考相关 APP 案例 圈友朱康分享高考相关的 APP。提到猿题库,其主要功能有练习册和猿辅导,都是收费的。猿题库出题给学生练习,将易错的总结起来出练习…...
AI的出现对计算机相关类型的博客或论坛的影响
最近越来越感觉到,AI的出现对计算机相关类型的博客是一种从寄生再到蚕食的过程。 在AI没出现之前,大家遇到问题,那一般都是去百度搜索,然后就能找到大神前辈的解答思路,这些解答思路基本都是写在博客或者论坛里的&…...
[LeetCode] 784. 字母大小写全排序
题目描述: 给定一个字符串 s ,通过将字符串 s 中的每个字母转变大小写,我们可以获得一个新的字符串。 返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。 示例 1: 输入:s "a1b2" 输出࿱…...

大数据Azkaban(二):Azkaban简单介绍
文章目录 Azkaban简单介绍 一、Azkaban特点 二、Azkaban组成结构 三、Azkaban部署模式 1、solo-server ode(独立服务器模式) 2、two server mode(双服务器模式) 3、distributed multiple-executor mode(分布式多…...
Vue3_开启全局websocket
1、封装websocket 新建文件夹"socket.ts",路径:"/utils/socket" export default (onMessage: Function) > {let socketUrl ws://171.29.8.218:8080/ems/ws/screen //socket请求地址let socket: WebSocketlet lockReconnect f…...
PTA 社交集群
当你在社交网络平台注册时,一般总是被要求填写你的个人兴趣爱好,以便找到具有相同兴趣爱好的潜在的朋友。一个“社交集群”是指部分兴趣爱好相同的人的集合。你需要找出所有的社交集群。 输入格式 输入在第一行给出一个正整数 N(≤1000&…...

USB Type-C 受电端取电快充协议芯片,支持PD+QC+FCP+SCP+AFC快充协议
前言 随着科技的飞速发展,电子设备对于快速充电的需求日益增加。为了满足这一需求,市场上涌现出了众多快充技术和产品。其中,XSP08Q诱骗取电芯片以其卓越的性能和广泛的应用场景,成为了快充领域的一颗璀璨明星。本文将对XSP08Q P…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...

工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...

SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...