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

【数据结构】 最大最小堆实现优先队列 python

堆的定义


堆(Heap)是一种特殊的完全二叉树结构,通常分为最大堆和最小堆两种类型。

在最大堆中,父节点的值总是大于或等于其子节点的值;

而在最小堆中,父节点的值总是小于或等于其子节点的值。

堆常用于实现优先队列,在许多算法中也有重要应用,比如堆排序、Dijkstra算法等。

堆的基本操作

  • 插入:向堆中添加一个新元素,并调整堆以保持其性质。

  • 删除:移除堆顶元素(最大或最小元素),并重新调整堆。

  • 获取最大/最小元素:直接访问堆顶元素即可获得。

堆的实现

Python 的 heapq 模块提供了对堆的支持,它实现了最小堆。以下是一个简单的例子:

import heapq# 创建一个空堆
heap = []# 向堆中插入元素
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
heapq.heappush(heap, 5)
print(heap)# 获取堆顶元素(最小元素)
min_element = heap[0]
print("堆顶元素:", min_element)# 移除堆顶元素
heapq.heappop(heap)
print("移除堆顶元素后的堆:", heap)# 如果需要使用最大堆,可以通过插入负值来模拟
max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -20)
heapq.heappush(max_heap, -5)
print(heap)max_element = -max_heap[0]  # 记得取负数得到原始的最大值
print("最大堆顶元素:", max_element)

注意:为了实现最大堆,我们需要存储元素的负值

因为 Python 标准库中的heapq 模块只提供最小堆的功能。



【模板】堆

题目描述

给定一个数列,初始为空,请支持下面三种操作:

  1. 给定一个整数 x x x,请将 x x x 加入到数列中。
  2. 输出数列中最小的数。
  3. 删除数列中最小的数(如果有多个数最小,只删除 1 1 1 个)。

输入格式

第一行是一个整数,表示操作的次数 n n n
接下来 n n n 行,每行表示一次操作。每行首先有一个整数 o p op op 表示操作类型。

  • o p = 1 op = 1 op=1,则后面有一个整数 x x x,表示要将 x x x 加入数列。
  • o p = 2 op = 2 op=2,则表示要求输出数列中的最小数。
  • o p = 3 op = 3 op=3,则表示删除数列中的最小数。如果有多个数最小,只删除 1 1 1 个。

输出格式

对于每个操作 2 2 2,输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

5
1 2
1 5
2
3
2

输出 #1

2
5

说明/提示

【数据规模与约定】

  • 对于 30 % 30\% 30% 的数据,保证 n ≤ 15 n \leq 15 n15
  • 对于 70 % 70\% 70% 的数据,保证 n ≤ 1 0 4 n \leq 10^4 n104
  • 对于 100 % 100\% 100% 的数据,保证 1 ≤ n ≤ 1 0 6 1 \leq n \leq 10^6 1n106 1 ≤ x < 2 31 1 \leq x \lt 2^{31} 1x<231 o p ∈ { 1 , 2 , 3 } op \in \{1, 2, 3\} op{1,2,3}

AC_code:

import heapq
hp = []
n = int(input())
for _ in range(n):a = list(map(int, input().split()))op = a[0]if op == 1:heapq.heappush(hp, a[1])elif op == 2:print(hp[0])else:heapq.heappop(hp)


实战演练


牛客周赛 Round 82 E题 和+和

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述


方法思路


我们需要从两个数组中选择2m个下标,使得前m个下标对应的a数组元素之和加上后m个下标对应的b数组元素之和最小。关键在于高效地找到这些下标的最优组合。
  1. 预处理前缀和后缀数组

    • pre_a[k]:表示在前k个元素中选择m个最小的a数组元素之和。
    • suf_b[k]:表示从第k个元素到末尾中选择m个最小的b数组元素之和。
  2. 使用大根堆维护最小元素

    • 遍历数组时维护一个大根堆,确保堆中始终保存当前最小的m个元素。当堆的大小超过m时,弹出最大的元素,保持堆的大小为m。
  3. 遍历所有可能的分割点

    • 对于每个可能的分割点k,计算前k个元素的最小m个a之和,加上从k+1到末尾的最小m个b之和,取最小值。

AC_code:

import heapqn, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))pre_a = [float('inf')] * (n + 1)
heap = []  # 最大堆(通过存储负数模拟)
sum_a = 0  for i in range(1, n + 1):heapq.heappush(heap, -a[i - 1])  # 将当前元素加入堆中(存入负数表示最大堆)sum_a += a[i - 1]  # 如果堆的大小超过 m,则移除堆顶元素(即最大的那个)if len(heap) > m:removed = -heapq.heappop(heap)sum_a -= removed# 如果堆中有正好 m 个元素,则记录当前的前缀和if len(heap) == m:pre_a[i] = sum_a# 初始化后缀和数组 suf_b
suf_b = [float('inf')] * (n + 2)
heap = []  # 清空堆
sum_b = 0 # 计算后缀和
for i in range(n, 0, -1):heapq.heappush(heap, -b[i - 1])  # 将当前元素加入堆中(存入负数表示最大堆)sum_b += b[i - 1]  # 如果堆的大小超过 m,则移除堆顶元素(即最大的那个)if len(heap) > m:removed = -heapq.heappop(heap)sum_b -= removed# 如果堆中有正好 m 个元素,则记录当前的后缀和if len(heap) == m:suf_b[i] = sum_bans = float('inf')
for k in range(m, n-m + 1):ans = min(ans, pre_a[k] + suf_b[k+1])print(ans)

代码解释

  1. 预处理前缀数组pre_a

    • 使用大根堆维护前k个元素中最小的m个元素之和。每次添加元素后,若堆的大小超过m,则弹出最大元素,保持堆的大小为m,确保sum_a始终是前k个元素中最小的m个之和。
  2. 预处理后缀数组suf_b

    • 从后往前遍历b数组,同样使用大根堆维护从当前元素到末尾的最小的m个元素之和。处理方式与pre_a类似,确保sum_b是当前处理段的最小m个元素之和。
  3. 遍历分割点k

    • 遍历所有可能的k值,计算pre_a[k](前k个元素的最小m个a之和)和suf_b[k+1](从k+1到末尾的最小m个b之和)的总和,取最小值作为结果。

这种方法利用堆高效地维护了最小的m个元素之和,预处理时间复杂度为O(n log m),遍历分割点的复杂度为O(n),整体复杂度为O(n log m),适用于大规模数据。


END
如果有更多问题或需要进一步的帮助,可以在评论区留言讨论哦!
如果喜欢的话,请给博主点个关注 谢谢

相关文章:

【数据结构】 最大最小堆实现优先队列 python

堆的定义 堆&#xff08;Heap&#xff09;是一种特殊的完全二叉树结构&#xff0c;通常分为最大堆和最小堆两种类型。 在最大堆中&#xff0c;父节点的值总是大于或等于其子节点的值&#xff1b; 而在最小堆中&#xff0c;父节点的值总是小于或等于其子节点的值。 堆常用于实…...

基于多层感知机(MLP)实现MNIST手写体识别

实现步骤 下载数据集处理好数据集确定好模型&#xff08;初始化模型参数等等&#xff09;确定优化函数&#xff08;损失函数也称为目标函数&#xff09;和优化方法&#xff08;一般选用随机梯度下降 SDG &#xff09;进行模型的训练进行模型的评估 import torch import torch…...

QT和有道词典有冲突,导致内存溢出,闪退。

提示&#xff1a;本文为学习记录&#xff0c;若有疑问&#xff0c;请联系作者。 前言 具体详细查看此博主&#xff1a;原文链接 在使用Qt Designer时&#xff0c;如果开启了有道词典&#xff0c;会导致Qt Designer崩溃。估计应该是把有道词典屏幕取词功能打开后&#xff0c;有…...

4. 示例:创建带约束的随机地址生成器(范围0x1000-0xFFFF)

文章目录 前言代码示例&#xff1a;运行方法&#xff1a;查看结果&#xff1a;关键功能说明&#xff1a;扩展功能建议&#xff1a; 前言 以下是一个完整的SystemVerilog测试平台示例&#xff0c;包含约束随机地址生成、日志输出和波形生成功能&#xff1a; 代码示例&#xff1…...

VSCode轻松调试运行C#控制台程序

1.背景 我一直都是用VS来开发C#项目的&#xff0c;用的比较顺手&#xff0c;也习惯了。看其他技术文章有介绍VS Code更轻量&#xff0c;更方便。所以我专门花时间来使用VS Code&#xff0c;看看它是如何调试代码、如何运行C#控制台。这篇文章是一个记录的过程。 2.操作 2.1 V…...

内容中台是什么?内容管理平台解析

内容中台的核心价值 现代企业数字化转型进程中&#xff0c;内容中台作为中枢系统&#xff0c;通过构建统一化的内容管理平台实现数据资产的高效整合与智能调度。其核心价值体现在打破传统信息孤岛&#xff0c;将分散于CRM、ERP等系统的文档、知识库、产品资料进行标准化归集&a…...

sqlmap:自动SQL注入和数据库接管工具

SQL 注入攻击是 Web 安全领域最常见的漏洞之一&#xff0c;今天给大家介绍一个自动化 SQL 注入和数据库接管工具&#xff1a;sqlmap。sqlmap 作为一款开源渗透测试工具&#xff0c;能帮助安全测试人员快速发现并利用 SQL 注入漏洞接管数据库服务器。 功能特性 sqlmap 使用 Pyt…...

Python设置阿里云镜像源教程:解决PIP安装依赖包下载速度慢的问题

在 Python 中&#xff0c;你可以通过修改 pip 的配置文件来设置阿里云镜像源&#xff0c;以加速包的安装。以下是具体步骤&#xff1a; 1. 临时使用阿里云镜像源 你可以在使用 pip 安装包时&#xff0c;通过 -i 参数临时指定阿里云镜像源&#xff1a; pip install <packa…...

基于专利合作地址匹配的数据构建区域协同矩阵

文章目录 地区地址提取完成的处理代码 在专利合作申请表中&#xff0c;有多家公司合作申请。在专利权人地址中&#xff0c; 有多个公司的地址信息。故想利用这里多个地址。想用这里的地址来代表区域之间的专利合作情况代表区域之间的协同、协作情况。 下图是专利合作表的一部分…...

Java集合List快速实现重复判断的10种方法深度解析

文章目录 引言&#xff1a;为什么需要关注List重复判断&#xff1f;一、基础实现方法1.1 暴力双循环法1.2 HashSet法 二、进阶实现方案2.1 Stream API实现2.2 TreeSet排序法 三、高性能优化方案3.1 并行流处理3.2 BitSet位图法&#xff08;仅限整数&#xff09; 四、第三方库实…...

List的模拟实现(2)

前言 上一节我们讲解了list的基本功能&#xff0c;那么本节我们就结合底层代码来分析list是怎么实现的&#xff0c;那么废话不多说&#xff0c;我们正式进入今天的学习&#xff1a;&#xff09; List的底层结构 我们先来看一下list的底层基本结构&#xff1a; 这里比较奇怪的…...

如何使用SaltStack批量替换SSL证书方案

以下是借助 SaltStack 批量替换 SSL 证书的完整方案&#xff0c;该方案结合了自动化更新与回滚机制&#xff0c;以保障操作的高效性与安全性&#xff1a; 一、准备工作 目录结构搭建 在 Salt Master 的 /home/salt/ssl_update 目录下构建如下结构&#xff1a;ssl_update/ ├──…...

Golang快速上手01/Golang基础

最近有需求&#xff0c;需要使用go&#xff0c;这几天快速过一遍基础语法&#xff0c;这是今天的总结 项目结构 #mermaid-svg-qpF09pnIik9bqQ4E {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-qpF09pnIik9bqQ4E .e…...

[Web 安全] 反序列化漏洞 - 学习笔记

关注这个专栏的其他相关笔记&#xff1a;[Web 安全] Web 安全攻防 - 学习手册-CSDN博客 0x01&#xff1a;反序列化漏洞 — 漏洞介绍 反序列化漏洞是一种常见的安全漏洞&#xff0c;主要出现在应用程序将 序列化数据 重新转换为对象&#xff08;即反序列化&#xff09;的过程中…...

【学习笔记】Google的Lyra项目:基于神经网络的超低比特率语音编解码技术

一、引言&#xff1a;语音通信的带宽挑战与技术突破 在实时音视频通信占据全球数字化生活核心地位的今天&#xff0c;Google于2021年推出的Lyra编解码器标志着语音编码技术进入新的时代。这款基于机器学习的新型音频编解码器以3kbps的极低比特率实现接近原始音质的语音重建能力…...

Unity Dedicated Server 控制台 输出日志LOg 中文 乱码

现象: 中文乱码 原因: Unity打包出来的.exe文件&#xff0c;语言一栏是英文&#xff0c;VS控制台出来不一样 解决方案: 新建.bat文件 &#xff0c;并使用命令chcp 65001&#xff0c;运行时启动.bat&#xff0c;而不是.exe, 改不了exe属性&#xff0c;虽然有点奇怪&#xff…...

【Excel】 Power Query抓取多页数据导入到Excel

抓取多页数据想必大多数人都会&#xff0c;只要会点编程技项的人都不会是难事儿。那么&#xff0c;如果只是单纯的利用Excel软件&#xff0c;我还真的没弄过。昨天&#xff0c;我就因为这个在网上找了好久发好久。 1、在数据-》新建查询-》从其他源-》自网站 &#xff0c;如图 …...

去耦电容的作用详解

在霍尔元件的实际应用过程中&#xff0c;经常会用到去耦电容。去耦电容是电路中装设在元件的电源端的电容&#xff0c;其作用详解如下&#xff1a; 一、基本概念 去耦电容&#xff0c;也称退耦电容&#xff0c;是把输出信号的干扰作为滤除对象。它通常安装在集成电路&#xf…...

HTTPS 与 HTTP 的区别在哪?

HTTP与HTTPS作为互联网数据传输的核心协议&#xff0c;其通信机制与安全特性深刻影响着现代网络应用的可靠性与用户体验。本文将解析两者的通信流程、安全机制及核心差异。 一、HTTP的通信机制 先来看看HTTP是什么吧。 HTTP基于TCP/IP协议栈&#xff0c;采用经典客户端-服务…...

let、const【ES6】

‌“我唯一知道的就是我一无所知。” - 苏格拉底 目录 块级作用域&#xff1a;var、let、const的对比&#xff1a;Object.freeze()&#xff1a; 块级作用域&#xff1a; 块级作用域指由 {} 包围的代码块&#xff08;如 if、for、while、单独代码块等&#xff09;形成的独立作用…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...