AcWing 839 模拟堆
使用堆（优先队列）维护集合，保持元素有序性。 渐进式插入，每次插入后进行上滤操作。 删除最小值时，考虑到最小值可能不唯一，选择交换最小值到堆末尾，再进行下滤。 删除第k个插入的元素时，找到其位置删除并调整堆结构。 修改元素时，找到位置修改值并进行上滤和下滤。
发布日期：2021-05-28 16:26:27
浏览次数：29
分类：精选文章
本文共 346 字，大约阅读时间需要 1 分钟。
维护一个集合，支持插入、删除最小值、删除第k个插入的元素以及修改第k个插入的数。每次PM操作时输出当前最小值。
实现思路：
关键问题：
- 如何实现在删除和修改第k个元素时，正确替换堆中的位置。
- 确保交换过程中数组ph和hp保持一致。
- 高效实现这些操作，适应较大数据量。
解决方案：
- 使用数组ph记录元素在堆中的下标，数组hp记录堆中元素在插入顺序中的位置。
- 交换节点时，交换对应的ph[和hp]。
- 调用上滤和下滤操作确保堆的结构正确。
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2025年04月25日 00时35分29秒
关于作者
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！
-- 愿君每日到此一游！
推荐文章
@ControllerAdvice用法
2023-01-23
#VERDI# 关于Verdi使用的几个常用技巧整理
2023-01-23
@Resource注解的使用
2023-01-23
@ResponseBody 和 @RequestBody
2023-01-23
A + B 九度oj
2023-01-23
A20地址线
2023-01-23
abaqus质量缩放系数取值_ABAQUS的质量缩放
2023-01-23
#systemverilog# 关于随机约束之 数组类型数据
2023-01-23
Accessibility
2023-01-23
08-信息收集之端口收集（总结版）
2023-01-23
15种下载文件的方法&文件下载方法汇总&超大文件下载
2023-01-23
anaconda、python卸载后重装以及anaconda--443
2023-01-23
AWVS工具太顶了，漏洞扫描工具AWVS介绍及安装教程
2023-01-23
CentOS 系列：CentOS 7文件系统的组成
2023-01-23
白红宇的个人博客 - 记录点点滴滴的事 - 您是第 462731446 位访客
访问时间: 2025-05-11 18:21:06
访问IP: 18.118.11.120
Copyright © 2020 - 2025 css8.cn 京ICP备2021015314号-1
手机版