当前位置: 首页 > news >正文

堆(堆排序,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

  1. 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 概念解释 堆的定义&#xff1a;堆是一颗完全二叉树&#xff0c;分为大堆和小堆 大堆&#xff1a;一棵树中&#xff0c;任何父亲节点都大于等于孩子的节点&#xff0c;大堆的根结点最大 小堆&#xff1a;一棵树中&#xff0c;任何父亲节点都小于等于孩子节点&#xff0c;小堆…...

(三)行为模式:11、模板模式(Template Pattern)(C++示例)

目录 1、模板模式含义 2、模板模式的UML图学习 3、模板模式的应用场景 4、模板模式的优缺点 5、C实现的实例 1、模板模式含义 模板模式&#xff08;Template Method Pattern&#xff09;是一种行为设计模式&#xff0c;它定义了一个操作中的算法骨架&#xff0c;将某些步骤…...

贝叶斯中的充分统计量

内容来源 贝叶斯统计&#xff08;第二版&#xff09;中国统计出版社 前两篇笔记简述经典统计中的充分统计量和判断充分统计量的 N e y m a n Neyman Neyman 因子分解定理 而在贝叶斯统计中&#xff0c;充分统计量也有一个充要条件 定理兼定义 设 x ( x 1 , x 2 , ⋯ , x …...

012:ArcGIS Server 10.2安装与站点创建教程

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

xlive.dll错误的详细解决办法步骤教程,xlive.dll基本状况介绍

在计算机的众多文件中&#xff0c;“xlive.dll”扮演着独特而重要的角色。所以当你的电脑丢失了xlive.dll文件时&#xff0c;会倒是电脑不能正常运行&#xff0c;那么出现这样的问题有什么办法可以将丢失的xlive.dll进行修复呢&#xff1f;今天这篇文章将和大家聊聊xlive.dll错…...

通俗易懂的餐厅例子来讲解JVM

餐厅版本 JVM&#xff08;Java虚拟机&#xff09;可以想象成一个虚拟的计算机&#xff0c;它能够运行Java程序。为了让你更容易理解&#xff0c;我们可以用一个餐厅的比喻来解释JVM&#xff1a; 菜单&#xff08;Java源代码&#xff09;&#xff1a; 想象一下&#xff0c;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 列表常用操作方法 列表类型是一种抽象数据类型&#xff0c;抽象数据类型定义了数据类型的操作方法。在本…...

Prompt提示词设计:如何让你的AI对话更智能?

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

2024-10月的“冷饭热炒“--解读GUI Agent 之computer use?phone use?——多模态大语言模型的进阶之路

GUI Agent 之computer use&#xff1f;phone use?——多模态大语言模型的进阶之路 1.最新技术事件浅析三、思考和方案设计工具代码部分1.提示词2.工具类API定义&#xff0c;这里主要看computer tool就够了 总结 本文会总结概括这一应用的利弊&#xff0c;然后给出分析和工具代…...

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 时态对吗&#xff1f; 有需要修改的吗&#xff1f;你可…...

关于在vue2中接受后端返回的二进制流并进行本地下载

后端接口返回&#xff1a; 前端需要在两个地方写代码&#xff1a; 1.封装接口处&#xff0c;responseType: blob 2.接收相应处 download() {if (this.selectionList.length 0) {this.$message.error("请选择要导出的数据&#xff01;");} else {examineruleExport…...

[BUG]warn(f“Failed to load image Python extension: {e}“)的解决办法

在使用LlaMa-Factory工具包时&#xff0c;安装好环境后&#xff0c;输入llamafactory-cli env查看llama-factory的版本等信息时&#xff0c;bash提醒&#xff1a; /home/ubuntu/anaconda3/envs/Llama-Factory/lib/python3.10/site-packages/torchvision/io/image.py:13: UserW…...

配置MUX VLAN 的实验配置

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

高考相关 APP 案例分享

文章首发于https://qdgithub.com/article/2032 一、核心内容 &#xff08;一&#xff09;高考相关 APP 案例 圈友朱康分享高考相关的 APP。提到猿题库&#xff0c;其主要功能有练习册和猿辅导&#xff0c;都是收费的。猿题库出题给学生练习&#xff0c;将易错的总结起来出练习…...

AI的出现对计算机相关类型的博客或论坛的影响

最近越来越感觉到&#xff0c;AI的出现对计算机相关类型的博客是一种从寄生再到蚕食的过程。 在AI没出现之前&#xff0c;大家遇到问题&#xff0c;那一般都是去百度搜索&#xff0c;然后就能找到大神前辈的解答思路&#xff0c;这些解答思路基本都是写在博客或者论坛里的&…...

[LeetCode] 784. 字母大小写全排序

题目描述&#xff1a; 给定一个字符串 s &#xff0c;通过将字符串 s 中的每个字母转变大小写&#xff0c;我们可以获得一个新的字符串。 返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。 示例 1&#xff1a; 输入&#xff1a;s "a1b2" 输出&#xff1…...

大数据Azkaban(二):Azkaban简单介绍

文章目录 Azkaban简单介绍 一、Azkaban特点 二、Azkaban组成结构 三、Azkaban部署模式 1、solo-server ode&#xff08;独立服务器模式&#xff09; 2、two server mode&#xff08;双服务器模式&#xff09; 3、distributed multiple-executor mode&#xff08;分布式多…...

Vue3_开启全局websocket

1、封装websocket 新建文件夹"socket.ts"&#xff0c;路径&#xff1a;"/utils/socket" export default (onMessage: Function) > {let socketUrl ws://171.29.8.218:8080/ems/ws/screen //socket请求地址let socket: WebSocketlet lockReconnect f…...

PTA 社交集群

当你在社交网络平台注册时&#xff0c;一般总是被要求填写你的个人兴趣爱好&#xff0c;以便找到具有相同兴趣爱好的潜在的朋友。一个“社交集群”是指部分兴趣爱好相同的人的集合。你需要找出所有的社交集群。 输入格式 输入在第一行给出一个正整数 N&#xff08;≤1000&…...

USB Type-C 受电端取电快充协议芯片,支持PD+QC+FCP+SCP+AFC快充协议

前言 随着科技的飞速发展&#xff0c;电子设备对于快速充电的需求日益增加。为了满足这一需求&#xff0c;市场上涌现出了众多快充技术和产品。其中&#xff0c;XSP08Q诱骗取电芯片以其卓越的性能和广泛的应用场景&#xff0c;成为了快充领域的一颗璀璨明星。本文将对XSP08Q P…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; 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 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...