当前位置: 首页 > news >正文

堆的相关知识点

目录

大小堆

堆的实现

堆的创建

堆的销毁

交换

向上调整

向下调整

弹出首个元素

取出首个元素

判空

堆插入


大小堆

大堆:最上面的数字是最小的,越往下越大

小堆:最上面的数字是最大的,越往下越小

堆的复杂程度:

由错位相减我们可以知道T(n)= n - log(n-1) = n,所以建堆的复杂程度为O(N)

堆的实现

堆的创建

void HPInit(HP* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}

堆的销毁

void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

交换


void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}

向上调整


void Adjustup(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;int parent = (child - 1) / 2;}else{break;}}
}

向下调整

void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] > a[child + 1])//先假设左孩子是小的{child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}

弹出首个元素

void HPPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}

取出首个元素

HPDataType HPTop(HP* php)
{assert(php);assert(php->size);return php->a[0];
}

判空


bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

堆插入


void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = (php->capacity == php->size == 0 ? 4 : php->capacity * 2);HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));//扩建的是字节if (tmp == NULL){printf("malloc faild");return;}}php->a[php->size] = x;php->size++;Adjustup(php->a, php->size - 1);
}

相关文章:

堆的相关知识点

目录 大小堆 堆的实现 堆的创建 堆的销毁 交换 向上调整 向下调整 弹出首个元素 取出首个元素 判空 堆插入 大小堆 大堆&#xff1a;最上面的数字是最小的&#xff0c;越往下越大 小堆&#xff1a;最上面的数字是最大的&#xff0c;越往下越小 堆的复杂程度&#…...

【Sass】常用全局sass高级函数,可使用原子化CSS减轻代码量,方便快速开发

文章目录 前言一、安装二、样式custom.scssflex.scsscolor.scssmargin-padding.scssorther 总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 针对style的预编译器为scss 转载自git前端知识库 原博主是B站up程序员郑清&#xff0c;可以看他的v3教程…...

MYSQL 第四次作业

任务要求&#xff1a; 具体操作&#xff1a; 新建数据库&#xff1a; mysql> CREATE DATABASE mydb15_indexstu; Query OK, 1 row affected (0.01 sec) mysql> USE mydb15_indexstu; Database changed 新建表&#xff1a; mysql> CREATE TABLE student( ->…...

depcheck 前端依赖检查

介绍 depcheck 是一款用于检测项目中 未使用依赖项 的工具。 depcheck 通过扫描项目文件&#xff0c;帮助你找出未被引用的依赖&#xff0c;从而优化项目。 优势&#xff1a; 简单易用: 仅需几个简单的命令&#xff0c;就能够扫描并列出未使用的依赖项&#xff0c;让你快速了…...

Qt/C++音视频开发79-采集websocket视频流/打开ws开头的地址/音视频同步/保存到MP4文件/视频回放

一、前言 随着音视频的爆发式的增长,各种推拉流应用场景应运而生,基本上都要求各个端都能查看实时视频流,比如PC端、手机端、网页端,在网页端用websocket来接收并解码实时视频流显示,是一个非常常规的场景,单纯的http-flv模式受限于最大6个通道同时显示,一般会选择ws-f…...

网络安全等级保护制度1.0与2.0的演进与变革

等保1.0概述 等保1.0是我国在网络安全领域迈出的重要一步&#xff0c;它于2008年正式发布。该版本的等保制度以《信息安全技术 信息系统安全等级保护基本要求》为核心标准&#xff0c;主要聚焦于信息系统的物理安全、网络安全、主机安全、应用安全和数据安全等方面的基础防护。…...

多线程优化API请求:CountDownLatch与PriorityBlockingQueue的应用

目录 前言 CountDownLatch是什么&#xff1f; PriorityBlockingQueue是什么&#xff1f; 场景描述 解决方案 定义统一工厂制造类 定义制造厂 定义客户请求实现 定义控制器 定义启动类 结果呈现 启动项目 请求制造操作 总结 前言 写这篇文章的缘由是因为之前在面…...

谷粒商城实战笔记-54-商品服务-API-三级分类-拖拽效果

文章目录 一&#xff0c;54-商品服务-API-三级分类-修改-拖拽效果1&#xff0c;el-tree控件加上允许拖拽的属性2&#xff0c;是否允许拖拽3&#xff0c;完整代码 一&#xff0c;54-商品服务-API-三级分类-修改-拖拽效果 本节的主要内容是给三级分类树形结构加上拖拽功能&#…...

AI大模型学习必备十大网站

随着人工智能技术的快速发展&#xff0c;AI大模型&#xff08;如GPT-3、BERT等&#xff09;在自然语言处理、计算机视觉等领域取得了显著的成果。对于希望深入学习AI大模型的开发者和研究者来说&#xff0c;找到合适的学习资源至关重要。本文将为大家推荐十大必备网站&#xff…...

Elasticsearch:Golang ECS 日志记录 - zap

ECS 记录器是你最喜欢的日志库的格式化程序/编码器插件。它们可让你轻松地将日志格式化为与 ECS 兼容的 JSON。 编码器以 JSON 格式记录日志&#xff0c;并在可能的情况下依赖默认的 zapcore/json_encoder。它还处理 ECS 错误格式的错误字段记录。 默认情况下&#xff0c;会添…...

关于线性代数(考研)

1.AE的特征值的问题 若λ是A的特征值&#xff0c;对应的特征向量是x&#xff0c;则Axλx&#xff0c;所以(AE)xAxExλxx(λ1)x&#xff0c;所以λ1是AE的特征值。所以若A的特征值是1&#xff0c;1&#xff0c;0&#xff0c;则AE的特征值就是11&#xff0c;11&#xff0c;01&am…...

【java基础】spring springMVC springboot 的区别

Spring, Spring MVC, 和 Spring Boot 是三个紧密相关的技术&#xff0c;它们都是由 Pivotal 团队&#xff08;原SpringSource&#xff09;开发的&#xff0c;主要用于构建企业级的Java应用程序。尽管它们在功能上有所交集&#xff0c;但各自也有独特的定位和用途。 Spring Fra…...

【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 开源项目热度排行榜(100分) - 三语言AC题解(Python/Java/Cpp)

🍭 大家好这里是清隆Coding ,一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 👏 感谢大家的订阅➕ 和 喜欢💗 🍿 最新华为OD机试D卷目录,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测,专栏文章质量平均 93 分 最新华为OD机试目录…...

大模型算法面试题(十一)

本系列收纳各种大模型面试题及答案。 1、说一下目前主流或前沿的预训练模型&#xff0c;包括nlp&#xff08;百度ERNIE3.0&#xff0c;华为NEZHA&#xff0c;openAI gpt-3&#xff0c;nvidia MegatronLM&#xff0c;macrosoft T5&#xff09;和cv&#xff08;我只知道CLIP&…...

CSS 基础知识

CSS(级联样式表)是设置 Web 内容样式的代码。CSS 基础知识将介绍入门所需的内容。我们将回答以下问题:如何将文本设置为红色?如何使内容显示在(网页)布局中的某个位置?如何用背景图片和颜色装饰我的网页? 什么是CSS? 像HTML一样,CSS不是一种编程语言。它也不是一种标…...

IntelliJ IDEA 和 Eclipse的区别

IntelliJ IDEA 和 Eclipse 是两个非常流行的 Java 集成开发环境&#xff08;IDE&#xff09;&#xff0c;它们各自具有不同的特点和优势。下面是它们之间的一些主要对比&#xff1a; 性能和资源使用 IntelliJ IDEA 被认为在某些方面更加智能&#xff0c;能够提供更好的代码分…...

Ansible之playbook剧本编写(二)

tags 模块 可以在一个playbook中为某个或某些任务定义“标签”&#xff0c;在执行此playbook时通过ansible-playbook命令使用--tags选项能实现仅运行指定的tasks。 playbook还提供了一个特殊的tags为always。作用就是当使用always作为tags的task时&#xff0c;无论执行哪一个t…...

力扣第二十九题——两数相除

内容介绍 给你两个整数&#xff0c;被除数 dividend 和除数 divisor。将两数相除&#xff0c;要求 不使用 乘法、除法和取余运算。 整数除法应该向零截断&#xff0c;也就是截去&#xff08;truncate&#xff09;其小数部分。例如&#xff0c;8.345 将被截断为 8 &#xff0c;-…...

解析三款热门的文献翻译工具:优势与使用指南

今儿咱们来聊聊那些让咱们头疼又不得不面对的事儿——文献翻译。在浩瀚的学术海洋里遨游时&#xff0c;遇到外文文献那是家常便饭&#xff0c;但语言障碍就像海上的迷雾&#xff0c;一不小心就能让你偏离航向。别担心&#xff0c;我这不就带着几款亲测好用的文献翻译神器来了嘛…...

git 过滤LFS文件下载

git config --global filter.lfs.smudge "git-lfs smudge --skip -- %f" git config --global filter.lfs.process "git-lfs filter-process --skip" 恢复下载 git config --global filter.lfs.smudge "git-lfs smudge -- %f" git config --g…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...