heap 算法函数
2024-10-21 18:54:44
这一系列函数是在做 这道题 时发现的
这道题空间卡的很死,是不能用数组存下所有数字进行快排的
后来又尝试用 \(multiset\) 优化空间,发现不行,可能是 \(multiset\) 还有结构性存储空间
遂再尝试插排,时间又过不了...
后来发现了 \(heap\) 系列函数可以做这道题,一方面可以支持对数组或者 \(vector\) 等存储空间较小的容器进行操作,一方面时间复杂度也与 \(multiset\) 方法一样
这里介绍一下 \(heap\) 系列函数
make_heap
make_heap
函数将现有的数据转化为一个(默认最大)堆
vector<int> vec = {1, 2, 3, 4};
make_heap(vec.begin(), vec.end()); // vec : 4 2 3 1
make_heap(vec.begin(), vec.end(), greater<int>()); // 最小堆,这里 greater<int> 后面加 () 是模板类生成一个临时对象传入 make_heap 函数
// 若使用 greater<int>() 构建最小堆,之后的函数都要加上 greater<int>()
push_heap
在堆的末尾添加一个元素后,通过push_heap
对容器进行维护使其满足堆性质
注意,使用这个函数需要保证除了新添加的元素,之前的元素已经构成了一个堆
vector<int> vec = {1, 2, 3, 4};
make_heap(vec.begin(), vec.end());
vec.push_back(5); // 堆末尾添加新元素
push_heap(vec.begin(), vec.end()); // 维护堆,堆结构大小 +1
pop_heap
将堆头元素弹出(具体实现是将堆头元素与堆尾元素交换)并再次调整,使得剩下的 \(n-1\) 个元素重新满足堆结构
vector<int> vec = {1, 2, 3, 4};
pop_heap(vec.begin(), vec.end()); // 堆顶弹出,堆结构大小 -1
sort_heap
sort_heap
的功能就相当于多次调用heap_pop
直到堆为空,这样就实现了对元素的排序
用 heap 系列函数再来解决以上问题就方便多了,贴下代码
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 1e5 + 1;
int a[MAX_N];
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= k; ++i) cin >> a[i];
make_heap(a + 1, a + k + 1);
for (int i = 1; i <= n - k; ++i) {
int x;
cin >> x;
if (x >= a[1]) continue;
a[k + 1] = x;
push_heap(a + 1, a + k + 2);
pop_heap(a + 1, a + k + 2);
}
cout << a[1] << endl;
return 0;
}
最新文章
- vi 的使用
- mysql 表被锁时,需要执行的命令
- DotNet程序集解析
- 推荐两款PC健康小软件
- 使用规则引擎Drools计算圆周率PI
- @Async java 异步方法
- jump_ur.php通知模板
- js基础 1.简单js 语法 关键字 保留字 变量
- synchronized简介
- 斗牛app上架应用宝、牛牛手机游戏推广、百人牛牛app应用开发、棋牌游戏上传、手游APP优化
- Linux如何安装VMware Tools
- Tabhost最纯净的实现方式
- Java基础--JDK的安装和配置
- Your ApplicationContext is unlikely to start due to a @ComponentScan of the default
- vs2015调试iisexpress无法启动的问题解决方案整理
- Hexo博客搭建以及Next主题美化的经验之谈
- Django web project
- kafka 的quick start(windows平台)
- swift 解决tableView的Y值偏移64问题
- Java中的Class.forName
热门文章
- Java中静态方法和实例方法
- Linux的常用命令符标注
- npm ERR! Failed at the node-sass@4.14.1 postinstall script.
- reduce()
- AUTOCAD——半径标注命令
- centos上安装python3.6环境和 pip3
- NSQ(6)-nsq相关策略
- ctp认证权限
- Nucmer+LINKVIEW实现序列水平的共线性分析
- k8s centos 79,用kuboard-spray装成功。低版本的。安装docker-ce,安装epel源