数据结构之堆——学习笔记

1.堆的简介:

 

接下来看一下堆的建立;

 

接下来是如何在堆中插入数据以及删除数据:

 

 

 

大根堆的插入操作类似只是改变了一下大于和小于符号,同时插入操作的时间复杂度为O(logn)。

 

 

 

 来看几个问题:

答案当然是不可以:

 

这样的话就能根据原堆的末尾数字的大小来判断是应该尝试将它往上还是下进行移动。

 来看看STL里面的优先队列:

 

 

 值得注意的是 用优先队列是没有clear操作的。

接下来看几道例题:

1.堆排序:

 

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int n,heap[N],x,len=0;
inline void up(int x){
	while(x>1 && heap[x]<heap[x/2]){
	swap(heap[x],heap[x/2]);
	x/=2;
	}
}
inline void down(int k){
	while(k+k<=len){
		int j=k+k;
		if(j+1<=len && heap[j+1]<heap[j]) ++j;
		if(heap[j]>=heap[k]) break;
		swap(heap[k],heap[j]);
		k=j;
	}
} 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x;
		heap[++len]=x;
		up(len);
	}
	for(int i=1;i<=n;i++){
		cout<<heap[1]<<' ';
		swap(heap[1],heap[len]);
		--len;
		down(1);
	}
	return 0;
}

事实上用优先队列来做会非常的简单:

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>>q;
const int N=1e5+100;
int n;
/*inline void up(int x){
	while(x>1 && heap[x]<=heap[x/2]){
		swap(heap[x],heap[x/2]);
		x/=2;
	}
}
inline void down(int x){
	while(x+x<=len){
		int y=x+x;
		if(y+1<=len && heap[y+1]<heap[y])  ++y;
		if(heap[y]>=heap[x]) break;
		swap(heap[y],heap[x]);
		x=y;
	}
}*/
int main(){
    cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		q.push(x);
	}	
	for(int i=1;i<=n;i++){
		cout<<q.top()<<' ';
		q.pop();
	}
	return 0;
}

使用小根堆的话是需要背一下优先队列的写法,有一点长。

接下来看一下第二题:

合并数列:

 这道题目的数据范围如果给的很小的话其实可以直接考虑模拟做法,但是实际上这道题目并没有那么的简单,接下来看代码,我在上面给了注释。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;//这里的N要比序列的个数上限设置的更大
int n,len,m;//n个序列,len代表当前读入的堆的序列的个数,m是最后要输出的数字个数
struct xulie{
	int v,delta;//v代表某一序列当前的堆顶元素,delta代表对应序列的k值
}heap[N];
//对新读入的序列试着将他往上面排的函数
inline void up(int x){
	while(x>1 && heap[x].v<=heap[x/2].v){
		swap(heap[x],heap[x/2]);
		x/=2;
	}
}
//将堆首的元素试着往下排
inline void down(int x){
	while(x+x<=len){
		int y=x+x;
		if(y+1<=len && heap[y+1].v<heap[y].v)  ++y;
		if(heap[y].v>=heap[x].v) break;
		swap(heap[y],heap[x]);
		x=y;
	}
}
int main(){
   cin>>n;
   for(int i=1;i<=n;i++){
       int k,b;
       cin>>k>>b;
       heap[++len].v=b;
       heap[len].delta=k;
       up(len);
   }
   cin>>m;
   for(int i=1;i<=m;i++){
   	cout<<heap[1].v<<' ';
   	heap[1].v+=heap[1].delta;
   	//输出堆顶序列这时候的值之后,对该序列的v值加一个delta并将加了之后的堆顶序列试着往下排
   	down(1);
   }
   return 0;
}

这道题的做法还是很有意思的。

接下来看一下第三个题:

大富翁游戏:

 费了九牛二虎之力,可算是搞明白了。。。

代码如下:

#include<bits/stdc++.h>
using namespace std;
struct Info{
	int v,pos;
}heap1[100001],heap2[100001];
int n,m,len1,len2,s1[100001],s2[100001];
inline void up1(int k){
	while(k>1 && heap1[k].v<heap1[k/2].v){
		swap(heap1[k],heap1[k/2]);
		s1[heap1[k].pos]=k;
		s1[heap1[k/2].pos]=k/2;
		k/=2;
	}
}
inline void down1(int k){
	while(k+k<=len1){
		int j=k+k;
		if(j+1<=len1 && heap1[j+1].v<heap1[j].v)
		++j;
		if(heap1[k].v<=heap1[j].v) break;
		swap(heap1[k],heap1[j]);
		s1[heap1[k].pos]=k;
		s1[heap1[j].pos]=j;
		k=j;
	}
}
inline void up2(int k){
	while(k>1 && heap2[k].v>heap2[k/2].v){
		swap(heap2[k],heap2[k/2]);
		s2[heap2[k].pos]=k;
		s2[heap2[k/2].pos]=k/2;
		k/=2;
	}
}
inline void down2(int k){
	while(k+k<=len2){
		int j=k+k;
		if(j+1<=len2 && heap2[j+1].v>heap2[j].v)
		++j;
		if(heap2[k].v>=heap2[j].v) break;
		swap(heap2[k],heap2[j]);
		s2[heap2[k].pos]=k;
		s2[heap2[j].pos]=j;
		k=j;
	}
}
int main(){
	cin>>n;
	len1=len2=0;
	for(int i=1;i<=n;i++){
		heap1[++len1].v=100;
		heap1[len1].pos=i;
		s1[i]=len1;
		up1(len1);
		heap2[++len2].v=100;
		heap2[len2].pos=i;
		s2[i]=len2;
		up2(len2);
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
		if(x==1){
			int y,z;
			cin>>y>>z;
			heap1[s1[y]].v+=z;
			up1(s1[y]);
			down1(s1[y]);
			heap2[s2[y]].v+=z;
			up2(s2[y]);
			down2(s2[y]);
		}
		else{
			cout<<heap2[1].v<<' '<<heap1[1].v<<endl;
		}
	}
	return 0;
}

这里代码中使用了两个堆,heap1heap2,分别用来维护最小堆和最大堆。s1s2 数组用来记录每个人在堆中的位置。代码中的堆结构的使用主要是为了在O(log n)的时间复杂度内找到当前最高和最低资金,以提高效率。在每次资金变动后,通过调整堆,保证堆顶元素分别是当前最小和最大资金。

最后一个题:动态中位数

这里是代码:

#include<bits/stdc++.h>
using namespace std;
int n;
priority_queue<int>a,b;
int main(){
	cin>>n;
	int x;
	cin>>x;
	a.push(x);
	cout<<a.top()<<' ';
	for(int i=1;i<=n/2;i++){
		int x,y,z=a.top();
		cin>>x>>y;
		if(x<z)
		a.push(x);
		else 
		b.push(-x);
		if(y<z)
		a.push(y);
		else 
		b.push(-y);
		if(a.size()-b.size()==3){
			b.push(-a.top());
			a.pop();
		} else 
		if(b.size()-a.size()==1){
			a.push(-b.top());
			b.pop();
		}
		cout<<a.top()<<' ';
	}
	return 0;
}

 

  1. priority_queue 的使用:定义了两个优先队列(堆),ab。它们用于存储输入数字,其中 a 是最大堆,b 是最小堆。

  2. 第一个数字的处理:从输入中读取第一个数字 x,将其压入最大堆 a 中,然后输出当前中位数(即最大堆的堆顶元素)。

  3. 循环处理每个数字对(x,y):

    • 如果 x 小于当前中位数(即最大堆的堆顶元素 a.top()),则将 x 压入最大堆 a
    • 否则,将 -xx 的相反数)压入最小堆 b
    • 如果 y 小于当前中位数,则将 y 压入最大堆 a
    • 否则,将 -yy 的相反数)压入最小堆 b
  4. 调整堆大小:在每次插入后,检查两个堆的大小关系:

    • 如果最大堆 a 的大小比最小堆 b 大 3,将最大堆的堆顶元素弹出并压入最小堆 b
    • 如果最小堆 b 的大小比最大堆 a 大 1,将最小堆的堆顶元素弹出并取其相反数压入最大堆 a
  5. 输出中位数:每次插入后,输出当前中位数(即最大堆的堆顶元素 a.top())。

  6. 这段代码通过维护最大堆和最小堆,根据输入的数字实时调整堆,以便高效地计算中位数。在中位数的计算过程中,通过在两个堆之间调整元素,确保了两个堆的大小差距在一个合理的范围内。这样做的目的是为了避免在求中位数时需要对所有数据进行排序的开销,从而实现更加高效的中位数计算

希望这一篇学习笔记对读者有所帮助,让我们共同进步。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/297946.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

3D人体姿态估计(教程+代码)

3D人体姿态估计是指通过计算机视觉和深度学习技术&#xff0c;从图像或视频中推断出人体的三维姿态信息。它是计算机视觉领域的一个重要研究方向&#xff0c;具有广泛的应用潜力&#xff0c;如人机交互、运动分析、虚拟现实、增强现实等。 传统的2D人体姿态估计方法主要关注通…

递归问题示例

斐波那契数列 f ( n ) { 1 n 1 1 n 2 f ( n − 1 ) f ( n − 2 ) n > 2 1 , 1 , 2 , 3 , 5 , 8 . . . \begin{aligned} f(n)\begin{cases}1&n1\\ 1&n2\\ f(n-1)f(n-2)&n\gt2 \end{cases}\\ 1,1,2,3,5,8\quad ... \end{aligned} f(n)⎩ ⎨ ⎧​11f(n−1)f(n−…

CMU15-445-Spring-2023-Project #1 - Buffer Pool

前置知识&#xff0c;参考上一篇博客&#xff1a;CMU15-445-Spring-2023-Project #1 - 前置知识&#xff08;lec01-06&#xff09; 在存储管理器中实现缓冲池。缓冲池负责将物理页从主内存来回移动到磁盘。它允许 DBMS 支持大于系统可用内存量的数据库。缓冲池的操作对系统中的…

spring boot 集成邮件发送功能

一、首先到QQ邮箱申请开启POP3、SMTP协议 二、安装依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-mail</artifactId></dependency><dependency><groupId>org.springframew…

【漏洞挖掘】挖掘CNVD证书

文章目录 一、CNVD介绍事件型漏洞通用型漏洞 二、挖掘思路1. 黑盒测试资产搜集fofa API筛选脚本 2. 白盒测试代码审计 3. google hack注意事项 一、CNVD介绍 国家信息安全漏洞共享平台&#xff08;简称CNVD&#xff09;&#xff0c;对于白帽子来说&#xff0c;挖掘的漏洞提交后…

关于谷歌Gemini大模型

2023年12月7日&#xff0c;谷歌AI宣布发布新一代基于Transformer架构的大模型Gemini。 Gemini的名字来源于双子座&#xff0c;象征着模型的双重性质&#xff1a; 一方面&#xff0c;它是一个强大的训练模型&#xff0c;可以在各种下游任务上进行微调&#xff0c;如文本摘要、机…

MiniTab的宏基础知识

什么是宏&#xff1f; 宏是包含一系列 Minitab 会话命令的文本文件。可以使用宏自动执行重复性任务&#xff08;例如&#xff0c;生成月度报表&#xff09;或扩展 Minitab 的功能&#xff08;例如&#xff0c;计算特殊检验统计量&#xff09;。 Minitab 提供以下类型的宏&…

计算机毕业设计选题分享-SSM律师事务所业务管理系统01664(赠送源码数据库)JAVA、PHP,node.js,C++、python,大屏数据可视化等

SSM律师事务所业务管理系统 摘 要 随着科学技术的飞速发展&#xff0c;社会的方方面面、各行各业都在努力与现代的先进技术接轨&#xff0c;通过科技手段来提高自身的优势&#xff0c;律师事务所业务管理系统当然也不能排除在外。律师事务所业务管理系统是以实际运用为开发背景…

CodeWave智能开发平台--03--目标:应用创建--04自定义主题样式5子页面页面跳转逻辑

摘要 本文是网易数帆CodeWave智能开发平台系列的第07篇&#xff0c;主要介绍了基于CodeWave平台文档的新手入门进行学习&#xff0c;实现一个完整的应用&#xff0c;本文主要完成04自定义主题样式5子页面页面跳转逻辑 参考:新手训练营-PC端应用 CodeWave智能开发平台的07次接…

NVIDIA Jetpack6.0DP使用过程中的问题

Jetpack6.0DP是2023年12月才发布&#xff0c; 操作系统使用了ubuntu 22.04&#xff0c; gcc是11.4&#xff0c;版本都很高&#xff0c; 用起来还存在一些问题 无法使用jtop https://forums.developer.nvidia.com/t/jtop-no-longer-works-on-jp-6-0-dp/275215 使用$ sudo -H p…

【JAVA】OPENGL+TIFF格式图片,不同阈值旋转效果

有些科学研究领域会用到一些TIFF格式图片&#xff0c;由于是多张图片相互渐变&#xff0c;看起来比较有意思&#xff1a; import java.io.IOException; import java.text.SimpleDateFormat; import java.util.Date; import java.util.logging.*;/*** 可以自已定义日志打印格式…

Oracle数据库新手零基础入门,Oracle安装配置和操作使用详解

一、教程描述 本套教程是专门为初学者量身定制的&#xff0c;无需任何Oracle数据库基础&#xff0c;课程采用循序渐进的教学方式&#xff0c;从Oracle数据库的基础知识开始讲起&#xff0c;并不会直接涉及到一项具体的技术&#xff0c;而是随着课程的不断深入&#xff0c;一些…

基于python的leetcode算法介绍之动态规划

文章目录 零 算法介绍一 例题介绍 使用最小花费爬楼梯问题分析 Leetcode例题与思路[118. 杨辉三角](https://leetcode.cn/problems/pascals-triangle/)解题思路题解 [53. 最大子数组和](https://leetcode.cn/problems/maximum-subarray/)解题思路题解 [96. 不同的二叉搜索树](h…

自动驾驶预测-决策-规划-控制学习(4):预测分析文献阅读

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、摘要分析1.Transformer模型是什么&#xff1f;什么是自注意力机制&#xff1f; 2.数据集是什么&#xff1f;3.预测车辆行驶轨迹和车辆换道意图4. LSTM 网络…

Pytest成魔之路 —— fixture 之大解剖!

1. 简介 fixture是pytest的一个闪光点&#xff0c;pytest要精通怎么能不学习fixture呢&#xff1f;跟着我一起深入学习fixture吧。其实unittest和nose都支持fixture&#xff0c;但是pytest做得更炫。 fixture是pytest特有的功能&#xff0c;它用pytest.fixture标识&#xff0c…

MybatisPlus—快速入门

目录 1.使用MybatisPlus的基本步骤 1.1引入MybatisPlus的起步依赖 1.2 定义Mapper 2.MybatisPlus常用注解 2.1 TableName 2.2 TableId 2.3 TableField 2.4 小结 3. 常用配置 4. 总结 1.使用MybatisPlus的基本步骤 1.1引入MybatisPlus的起步依赖 MyBatisPlus官方提…

如何使用 NFTScan NFT API 在 PlatON 网络上开发 Web3 应用

PlatON 是由万向区块链和矩阵元主导开发的面向下一代的全球计算架构&#xff0c;创新性的采用元计算框架 Monad 和基于 Reload 覆盖网络的同构多链架构&#xff0c;其愿景是成为全球首个提供完备隐私保护能力的运营服务网络。它提供计算、存储、通讯服务&#xff0c;并提供算力…

软件测试|什么是Python构造方法,构造方法如何使用?

构造方法&#xff08;Constructor&#xff09;是面向对象编程中的重要概念&#xff0c;它在创建对象时用于初始化对象的实例变量。在Python中&#xff0c;构造方法是通过特殊的名称__init__()来定义的。本文将介绍Python构造方法的基本概念、语法和用法。 什么是构造方法&…

React使用动态标签名称

最近在一项目里&#xff08;React antd&#xff09;遇到一个需求&#xff0c;某项基础信息里有个图标配置&#xff08;图标用的是antd的Icon组件&#xff09;&#xff0c;该项基础信息的图标信息修改后&#xff0c;存于后台数据库&#xff0c;后台数据库里存的是antd Icon组件…

ArkTS - 网络请求

一、Axios请求 应用通过HTTP发起一个数据请求&#xff0c;支持常见的GET、POST、OPTIONS、HEAD、PUT、DELETE、TRACE、CONNECT方法。 前端开发肯定都使用过一个叫axios的第三方库&#xff0c;它是是一个基于 promise 的网络请求库&#xff0c;可以用于浏览器和 node.js&…