当前位置: 首页 > 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…...

轻量级工具G-Helper:一站式解决ROG游戏本色彩配置异常问题

轻量级工具G-Helper&#xff1a;一站式解决ROG游戏本色彩配置异常问题 【免费下载链接】g-helper Lightweight Armoury Crate alternative for Asus laptops. Control tool for ROG Zephyrus G14, G15, G16, M16, Flow X13, Flow X16, TUF, Strix, Scar and other models 项目…...

SDMatte+边缘精修效果展示:羽毛建模精度、纱布透光过渡、叶片脉络保留

SDMatte边缘精修效果展示&#xff1a;羽毛建模精度、纱布透光过渡、叶片脉络保留 1. 惊艳效果开场 想象一下这样的场景&#xff1a;你需要为一件羽毛饰品拍摄产品图&#xff0c;但无论怎么调整灯光和背景&#xff0c;羽毛边缘总是显得模糊不清&#xff1b;或者当你尝试抠出一…...

从ImageNet到CV落地:深度解读AlexNet的6个工程优化技巧

从AlexNet到现代CV工程&#xff1a;6个历久弥新的优化策略解析 当AlexNet在2012年ImageNet竞赛中以压倒性优势夺冠时&#xff0c;它带来的不仅是准确率的飞跃&#xff0c;更是一套影响深远的工程实践方法论。十年过去&#xff0c;尽管网络架构已迭代数十代&#xff0c;但AlexNe…...

建议收藏|降AIGC工具深度测评与2026年最好用推荐

2026年真正好用的AI论文降重与改写工具&#xff0c;核心看降重效果、去AI味、格式保留、学术适配四大指标。综合实测&#xff0c;千笔AI、ThouPen、豆包、DeepSeek、Grammarly 是当前最值得推荐的梯队&#xff0c;覆盖从免费到付费、从中文到英文、从文科到理工的全场景需求。 …...

SDXL-Turbo在虚拟现实中的应用:实时环境生成技术

SDXL-Turbo在虚拟现实中的应用&#xff1a;实时环境生成技术 想象一下&#xff0c;在虚拟世界中每走一步&#xff0c;周围的景色就随之变化——茂密的森林在你眼前生长&#xff0c;古老的城堡在远处拔地而起&#xff0c;这一切都发生在眨眼之间。这不是魔法&#xff0c;而是SDX…...

建行江门市分行:量身定制金融策 陈皮产业绽新姿

“前期承包土地、购买柑苗已投入大量资金&#xff0c;后续还要设法购买化肥。”眼看资金接续不上&#xff0c;前期投入面临打水漂&#xff0c;流动资金短缺让江门新会某陈皮庄园负责人老李一筹莫展。 获悉老李困境后&#xff0c;建行广东江门分行网点客户经理驱车前往果园实地走…...

Python AI 用例工具部署踩坑实录:Docker镜像体积暴增300%、GPU显存泄漏、模型热加载失败的5个根因与秒级修复方案

第一章&#xff1a;Python AI 用例工具部署的典型失败图谱在真实生产环境中&#xff0c;Python AI 工具链&#xff08;如 LangChain、LlamaIndex、FastAPI 封装的推理服务&#xff09;的部署失败往往并非源于模型能力缺陷&#xff0c;而是由基础设施、依赖冲突与配置漂移引发的…...

终极桌面歌词解决方案:LyricsX 让你的音乐体验全面升级

终极桌面歌词解决方案&#xff1a;LyricsX 让你的音乐体验全面升级 【免费下载链接】Lyrics Swift-based iTunes plug-in to display lyrics on the desktop. 项目地址: https://gitcode.com/gh_mirrors/lyr/Lyrics 在macOS平台上享受音乐时&#xff0c;你是否曾渴望拥有…...

OpenCore Legacy Patcher终极指南:让你的老Mac焕发新生,体验最新macOS

OpenCore Legacy Patcher终极指南&#xff1a;让你的老Mac焕发新生&#xff0c;体验最新macOS 【免费下载链接】OpenCore-Legacy-Patcher 体验与之前一样的macOS 项目地址: https://gitcode.com/GitHub_Trending/op/OpenCore-Legacy-Patcher 你是否还在为老旧的Mac无法升…...

CosyVoice语音克隆应用案例:为短视频配音、制作个性化语音问候消息

CosyVoice语音克隆应用案例&#xff1a;为短视频配音、制作个性化语音问候消息 最近帮朋友做短视频账号&#xff0c;发现一个挺头疼的问题&#xff1a;每次拍完视频&#xff0c;找配音特别麻烦。要么自己录&#xff0c;口音重还费时间&#xff1b;要么用AI配音&#xff0c;声音…...