当前位置: 首页 > 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;形成的独立作用…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

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…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...