数据结构-堆的实现和应用

server/2024/11/28 7:26:13/

目录

1.堆的概念

2.堆的构建

3.堆的实现

4.堆的功能实现

4.1堆的初始化

4.2堆的销毁

4.3堆的插入

4.3.1向上调整

4.4堆的删除

4.4.1向下调整法

​编辑4.5取堆顶

5. 向上调整法和向下调整法比较

 6.堆的应用

6.1TOP-K问题

6.2TOP-K思路

6.2.1用前n个数据来建堆

6.2.2剩下的N-K 

6.3示例


1.堆的概念

堆的底层是数组,所以堆也是一种特殊的数组。

堆分为大堆和小堆

  • 大堆:父节点不小于子节点
  • 小堆:父节点不大于子节点

2.堆的构建

已经提到堆是一种数组,那么要怎么实现呢。

先以小堆为例,已知父节点不小于子节点,使用数组,数组下标0是根节点,1和2是他的子节点,接着1的子节点是3和4,2的子节点是5和6,这样就可以实现一个堆了。

3.堆的实现

既然是数组,就要有指针,容量大小。

4.堆的功能实现

4.1堆的初始化

4.2堆的销毁

4.3堆的插入

一直到这一步,都是和栈是相同的,因为我们插入数据了,这时我们无法保证这是一个堆,所以此时要进行向上调整。

4.3.1向上调整

因为此时插入是数据再最下面,所以要和上面的进行比较调整。

4.4堆的删除

我们是删除堆的最后一个元素,要怎么删除呢,我们可以将最后一个元素和第一个元素进行交换,然后使堆向下调整即可。

        

4.4.1向下调整法

4.5取堆顶

5. 向上调整法和向下调整法比较

推导时间复杂度,由于用图来表示有些难度,这里直接用笔写出来

这是向下调整法的推导过程

向下调整建堆的时间复杂度如图

下面是向上调整建堆的时间复杂度推导

总结:向上调整算法建堆是优于向下调整建堆的。

 6.堆的应用

6.1TOP-K问题

这种问题通常是在较大的数据样本中取出其中的最值,这时就可以通过堆来完成。

通常这类问题样本较大,排序就不太可取,可以建堆来实现。

6.2TOP-K思路

6.2.1用前n个数据来建堆

求最大的前n个就建小堆

求最小的前n个就建大堆

6.2.2剩下的N-K 

用剩下的N-K个数据来和堆顶数据比较,不满足就替换堆顶元素

6.3示例

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
#include<time.h>
void test()
{HP hp;HPInit(&hp);HPPush(&hp, 2);HPPush(&hp, 4);HPPush(&hp, 1);HPPush(&hp, 1); printf("%d", HPTop(&hp));}
void CreateNDate()
{int n = 10000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (file == NULL){perror("fopen fail");return;}for (int i = 0; i < n; i++){int x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}
void topk()
{int k = 0;printf("输入k的值\n");scanf("%d", &k);const char* file = "data.txt";FILE* fout = fopen(file, "r");int* arr = (int*)malloc(sizeof(int) * k);for (int i = 0; i < k; i++){fscanf(fout, "%d", &arr[i]);}//建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, k);}int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > arr[0]){arr[0] = x;AdjustDown(arr, 0, k);}}for (int i = 0; i < k; i++) {printf("%d ", arr[i]);}fclose(fout);
}int main()
{CreateNDate();topk();return 0;
}


http://www.ppmy.cn/server/145561.html

相关文章

天通物联网应用:首创渐进式图片压缩算法,实现1000倍高效图传,可一键拨打天通电话

一、天通卫星物联网应用 &#xff08;一&#xff09;天通卫星发展历程 汶川地震后&#xff0c;国家提出建设自己的移动通信卫星&#xff0c;以确保在严重自然灾害时的应急通信需求。2011年国家立项研制建设独立自主的卫星移动通信系统。2016年天通一号01星在我国西昌卫星发射…

2024算法基础公选课练习七(BFS1)

一、前言 还是偏基础的bfs&#xff0c;但是有几个题不是很好写 二、题目总览 三、具体题目 3.1 问题 A: 数据结构-队列-奇怪的电梯 我的代码 可以看成求一维平面的bfs最短路 #include <bits/stdc.h> using i64 long long; using pii std::pair<int,int>; co…

Mybatis---MyBatis映射文件SQL深入、多表查询

目录 第一章&#xff1a;MyBatis映射文件SQL深入 1.动态SQL 语句之if标签 2. 动态SQL语句之where标签 3. 动态SQL语句之foreach标签 4. 提取公用的SQL语句 提取公用SQL片段 定义分页模板 第二章&#xff1a;多表查询 1. 多表设计 2.搭建开发的环境 3.多对一查询&…

关于按天切割Tomcat的catalina.out日志文件的配置

1、catalina.out 是 Tomcat 的标准输出和标准错误日志&#xff0c;通常输出到 Tomcat 安装目录下的 logs 文件夹中。这个日志文件会记录 Tomcat 启动、停止以及运行过程中产生的所有日志信息。 2、在Apache Tomcat中&#xff0c;日志文件catalina.out默认情况下不会自动按天切割…

.NET9 - Swagger平替Scalar详解(四)

书接上回&#xff0c;上一章介绍了Swagger代替品Scalar&#xff0c;在使用中遇到不少问题&#xff0c;今天单独分享一下之前Swagger中常用的功能如何在Scalar中使用。 下面我们将围绕文档版本说明、接口分类、接口描述、参数描述、枚举类型、文件上传、JWT认证等方面详细讲解。…

Kubernetes 还是 SpringCloud?

前些年&#xff0c;随着微服务的概念提出以及落地&#xff0c;不断有很多的公司都加入到了这场技术革新中&#xff0c;现在可谓是人人都在做和说微服务。 提到微服务&#xff0c;Java栈内&#xff0c;就不得不提SpringBoot、SpringCloud、Dubbo。 近几年&#xff0c;随着Cloud …

远离网上的广告和无用信息,自己动手搭建Tipask问答网站

文章目录 前言1.Tipask网站搭建1.1 Tipask网站下载和安装1.2 Tipask网页测试1.3 cpolar的安装和注册 2. 本地网页发布2.1 Cpolar临时数据隧道2.2 Cpolar稳定隧道&#xff08;云端设置&#xff09;2.3 Cpolar稳定隧道&#xff08;本地设置&#xff09; 3. 公网访问测试4. 结语 前…

C++——多态(下)

目录 引言 多态 4.多态的原理 4.1 虚函数表指针 4.2 多态的原理 5.单继承和多继承关系的虚函数表 5.1 单继承中的虚函数表 5.2 多继承中的虚函数表 结束语 引言 接下来我们继续学习多态。 没有阅读多态&#xff08;上&#xff09;的可以点击下面的链接哦~ C——多态…