【数据结构】堆和集合笔记

  1. 自己写一个堆

首先,明确一下,为什么需要堆?

=>考虑插入,删除,查找的效率。

数组,查找,最快是二分查找O(lgN)。但查找完如果要做什么操作,比如删除,就要挪动元素了。所以合起来效率是O(lgN)+O(N)=O(N)

二叉树,看起来是O(lgN),但之前写树的时候有说过,链表是不是树?是树的退化形态,每个结点都有小于等于一个的儿子。这个时候查找的效率是O(lgN)了。之前说,查找之后万一要做什么操作,树就可能不是完全二叉树,即查找效率为O(lgN)。

能不能试图用平衡二叉树?不能,rotate非常麻烦。

=>所以尝试保持一颗完全二叉树=>给这棵树起名堆。

接下来考虑需要用什么基础的数据结构存储。

需要指针吗?

完全二叉树是每一个结点要么没有儿子,要么有两个儿子,在堆里只有最后一个有儿子的父节点可以只有左儿子。所以完全可以用数组表示。

假如链表下标从1开始,2和3是它的子节点,2/2=1,3/2=1,父节点访问也很方便。

  1. 初始化

表示这棵树需要几个数据:总容量,现在有多少元素,以及存放元素的数组。

初始化需要提供总容量。

  1. 插入元素

为确保是一个完全二叉树,插在最后。

堆需要确保一件事情,小元素在上,大元素在下。所以需要向上进行一次数据交换,寻找插入值的最终位置。

注意,这里说的是寻找,不需要真的交换,只需要挪动不符合要求的元素,找到插入值的最终位置赋值即可。

  1. 删除元素

删除一定是删最小的。其余和插入一样。

为确保是一个完全二叉树,将最后一个元素和被删除的第一个元素交换,然后向下寻找最终位置。

4. 一个数组的插入

为了保证堆的性质,插入数组后需要排序。

思考一下,哪些需要排序?

如果向下调整位置,则叶子结点不需要轮。如果向上调整位置,则根节点不需要轮。

效率为重,叶子结点最多,如果向上调整,则叶子结点需要轮的距离最远。而事实上,叶子结点又占了树结点的很大一部分。

所以我们选择向下调整。

完整代码(包括测试)

#include<iostream>
using namespace std;
class h{
private:
    int *nums;
    int capacity;
    int l;
public:
    h(){
        capacity=0;
    }
    void init(int c=1){
        capacity=c;
        l=0;
        nums=new int [c+1];
    }
    void printh(){
        for(int i=1;i<=l;i++){
            cout<<nums[i]<<" ";
        }cout<<endl;
    }
    int isfull(){
        if(capacity==l){
            return 1;
        }
        return 0;
    }
    void moveup(int k){
        int tempnum=nums[k];
        int i=k;
        for(i;tempnum<nums[i/2]&&i>1;i/=2){
            nums[i]=nums[i/2];
        }
        nums[i]=tempnum;
    }
    int insert(int n){
        if(isfull()){return 0;}
        nums[l+1]=n;
        l++;
        moveup(l);
        return 1;
    }
    int isempty(){
        if(l==0){
            return 1;
        }
        return 0;
    }
    void movedown(int k){
        int tempnum=nums[k];
        int i=k;
        while(i*2<=l){
            int child=i*2;
            if(child<l){
                if(nums[child]>nums[child+1]){
                    child++;
                }
            }
            if(nums[child]<tempnum){
                nums[i]=nums[child];
                i=child;
            }
            else{
                nums[i]=tempnum;
                return ;
            }
        }
        nums[i]=tempnum;
        return ;
    }
    int remove(){
        if(isempty()){return 0;}
        nums[1]=nums[l];
        l--;
        movedown(1);
        return 1;
    }
    void buildheap(int *a,int len,int c=0){
        if(len>c){c=len;}
        init(c);
        l=len;
        for(int i=0;i<len;i++){
            nums[i+1]=a[i];
        }
        for(int i=len/2;i>=1;i--){
            movedown(i);
        }
    }
};
int main(){
    int a[6]={10,50,60,5,30,20};
    h h1;
    h1.buildheap(a,6);
    h1.printh();
}

2. c++的堆

堆在queue中,叫priority_queue,默认是大顶堆,即树根是最大的元素,可以执行一下验证。

所以插入是push,查看堆顶元素是top(),弹出堆顶是pop()。

#include<iostream>
#include<queue>
using namespace std;
int main(){
    priority_queue<int>q1;
    int a[6]={111,222,333,11,22};
    for(int i=0;i<5;i++){
        q1.push(a[i]);
    }
    cout<<q1.top()<<endl;
    q1.pop();
    cout<<q1.top()<<endl;
}

堆额外有一种方法让其变为小顶堆,即提供一个容器,前提是这个容器支持从小到大排序,比如vector。

可以借助以下程序验证。

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main(){
    priority_queue<int,vector<int>,greater<int> >q1;
    int a[5]={111,222,333,11,22};
    for(int i=0;i<5;i++){
        q1.push(a[i]);
    }
    for(int i=0;i<5;i++){
        cout<<q1.top()<<endl;
        q1.pop();
    }
}

3. c++的集合

集合就是set嘛,之前刷题用了好多次了。

注意三点:

  1. set默认从小到大排序(因为底层实现是红黑树,类似AVL树)

  1. set.insert()也可以插入集合,方法详见下方实验代码

  1. 对于力扣中要求返回vector但你用set做了,只要返回{set.begin(), set.end()}即可

可以用以下代码验证set

#include<iostream>
#include<set>
using namespace std;
int main(){
    set<int>s1;
    int a1[3]={333,222,111};
    for(int i=0;i<3;i++){
        s1.insert(a1[i]);
    }
    for(auto x:s1){
        cout<<x<<" ";
    }cout<<endl;
    set<int>s2;
    s2.insert(666);
    s2.insert(555);
    s1.insert(s2.begin(),s2.end());
    for(auto x:s1){
        cout<<x<<" ";
    }cout<<endl;
}

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

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

相关文章

【Linux】进程的程序替换

文章目录1. 程序替换1.创建子进程的目的是什么&#xff1f;2.了解程序是如何进行替换的3. 程序替换的基本原理当创建进程的时候&#xff0c;先有进程数据结构&#xff0c;还是先加载代码和数据&#xff1f;程序替换是整体替换&#xff0c;不是局部替换execl 返回值4. 替换函数1…

【三维几何学习】从零开始网格上的深度学习-2:卷积网络CNN篇(Pytorch)

本文参加新星计划人工智能(Pytorch)赛道&#xff1a;https://bbs.csdn.net/topics/613989052 从零开始网格上的深度学习-2:卷积网络CNN篇引言一、概述1.1 卷积操作简述1.2 网格上的面卷积二、核心代码2.1 面卷积2.2 网络框架三、基于CNN的网格分类3.1 分类结果3.2 全部代码引言…

FPGA之时钟规划图解

目录 一、前言 二、时钟规划概念 三、时钟规划的模块 四、时钟规划之时钟单元布局 4.1 BUFG 4.2 BUFH 4.3 BUFR 4.4 BUFIO 五、时钟规划之时钟单元走线 5.1 BUFG->BUFH 5.2 BUFR->FF 5.3 BUFIO->FF 一、前言 对于vivado这类使用verilog语言的进…

《Netty》从零开始学netty源码(七)之NioEventLoop.selectStrategy

NioEventLoop是一个事件轮询器&#xff0c;在它的run方法中其实是一个for死循环&#xff0c;不断重复三个过程&#xff1a;1. 获取IO事件&#xff0c;2. 处理IO事件&#xff0c;3. 处理任务队列中的task&#xff0c;而SelectStractegy就是用于第一步获取IO事件&#xff0c;它的…

css:使用filter和backdrop-filter实现高斯模糊效果

背景 今天接到一个需求是&#xff0c;使用高斯模糊的效果对一个页面进行模糊处理&#xff0c;正好借这个机会来整理一下 css3 中高斯模糊的两个 API API介绍 filter 说明&#xff1a; 该 API 是一个过滤器&#xff0c;不仅能实现高斯模糊&#xff0c;还有很多比如颜色偏移、…

接口文档包含哪些内容?怎么才能写好接口文档?十年测试老司机来告诉你

目录 接口文档结构 参数说明 示例 错误码说明 语言基调通俗易懂 及时更新与维护 总结 那么我们该如何写好一份优秀的接口文档呢&#xff1f; 接口文档结构 首先我们要知道文档结构是什么样子的。接口文档应该有清晰明确的结构&#xff0c;以便开发人员能快速定位自己需…

经典文献阅读之--Dynamic-VINS(动态点滤除VINS)

0. 简介 现在的SLAM算法在静态环境中表现良好&#xff0c;但在动态环境中很容易失败。最近的工作将基于深度学习的语义信息引入到SLAM系统以减轻动态对象的影响。然而&#xff0c;在资源受限的机器人的动态环境中应用鲁棒定位仍然具有挑战性。所以《RGB-D Inertial Odometry f…

ES+Redis+MySQL,这个高可用架构设计太顶了!

一、背景 会员系统是一种基础系统&#xff0c;跟公司所有业务线的下单主流程密切相关。如果会员系统出故障&#xff0c;会导致用户无法下单&#xff0c;影响范围是全公司所有业务线。所以&#xff0c;会员系统必须保证高性能、高可用&#xff0c;提供稳定、高效的基础服务。 …

vue笔记

第一个Vue应用 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta http-equiv"X-UA-Compatible" content"IEedge" /><meta name"viewport" content"widthdevice-…

【零基础入门前端系列】—动画和弹性盒模型(二十四)

【零基础入门前端系列】—动画和弹性盒模型&#xff08;二十四&#xff09; 一、概念 动画是使元素从一种样式逐渐变化为另一种样式&#xff0c;你可以改变任意多的样式任意多的次数。 请用百分比来规定变化发生的时间&#xff0c;或用关键词from和to&#xff0c;等同0%和10…

购物清单(蓝桥杯C/C++省赛)

目录 1 问题描述 2 文件的读取格式 3 代码实现 1 问题描述 小明刚刚找到工作&#xff0c;老板人很好&#xff0c;只是老板夫人很爱购物。老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦&#xff0c;但又不好推辞。 这不&#xff0c;XX大促销又来了&#xff01;老板…

项目实战典型案例26——nacos的命名空间名称和id不一致带来的思考

nacos的命名空间名称和id不一致带来的思考一&#xff1a;背景介绍Nacos命名空间相关知识点思考总结一&#xff1a;背景介绍 项目用的naocs做的配置中心和服务发现。由于开发环境和本地环境使用的都是同一个命名空间&#xff0c;我们多个服务相互调用的时候&#xff0c;由于开发…

若依分离版下拉框动态加载

最近在学习使用若依分离版框架&#xff0c;想要实现下拉框动态加载另一张表的数据&#xff0c;于是参考【字典数据-字典名称】的实现方式&#xff0c;成功试下下拉框动态加载&#xff0c;做下记录 涉及表格&#xff1a;his_user&#xff08;用户表&#xff09;-- 用户管理&…

【linux】:进程概念

文章目录 冯诺依曼体系结构一&#xff1a;操作系统二: 进程总结冯诺依曼体系结构 我们常见的计算机&#xff0c;如笔记本。我们不常见的计算机&#xff0c;如服务器&#xff0c;大部分都遵守冯诺依曼体系。 冯诺依曼体系如下图&#xff1a; 那么输入设备有哪些呢&#xff1f…

常见的Web安全漏洞:SYN攻击/CSRF/XSS

一、SYN攻击&#xff08;属于DOS攻击&#xff09; 什么情况下被动方出现SYN_RCVD状态?(flood攻击服务) 客户伪造 ip 端口&#xff0c; 向服务端发送SYN请求。完成2次握手&#xff0c;第三次服务端 等待客户端ACK确认&#xff0c;但由于客户不存在服务端一直未收到确认&#…

内含18禁~~关于自学\跳槽\转行做网络安全行业的一些建议

作者&#xff1a;Eason_LYC 悲观者预言失败&#xff0c;十言九中。 乐观者创造奇迹&#xff0c;一次即可。 一个人的价值&#xff0c;在于他所拥有的。所以可以不学无术&#xff0c;但不能一无所有&#xff01; 技术领域&#xff1a;WEB安全、网络攻防 关注WEB安全、网络攻防。…

金三银四,我猜你需要这套网络安全工程师面试题合集

2023年已经开始了&#xff0c;先来灵魂三连问&#xff0c;年初定的目标是多少&#xff1f;薪资能涨吗&#xff1f;女朋友能找到吗&#xff1f; 好了&#xff0c;不扎大家的心了&#xff0c;接下来进入正文。 由于我之前写了不少网络安全技术相关的文章和回答&#xff0c;不少…

过来人告诉你:Java学到什么程度可以找工作?

大部分初次学习Java的同学都非常关注自己学到什么程度可以找工作就业&#xff0c;因为学习的目的一方面在于掌握知识、提高技能&#xff0c;另一方面就是就业谋生。今天笔者就来跟大家聊一聊一下Java学习到什么地步可以面试找工作。任何企业&#xff0c;不论大小&#xff0c;对…

exe反编译为.py文件

介绍公司以前的一个exe包&#xff0c;我们需要查看里面python源码&#xff0c;但是以前的py源码文件找不到&#xff0c;所以只能反编译&#xff0c;介绍一下反编译的过程。首先准备&#xff1a;pyinstxtractor.py这个文件&#xff0c;网上很多&#xff0c;自己下载准备查看二进…

十八、动画与canvas

1.RequestAnimationFrame 早期定时动画 setTimeout和setInterval不能保证时间精度&#xff0c;第二个参数只能保证何时将代码添加到浏览器的任务队列 requestAnimationFrame(cb)的cb在浏览器重绘屏幕前调用 function updateProgress(){const div document.getElementById(d…
最新文章