目录

一、堆的概念及结构

二、小根堆的实现

2.1 堆的数据结构

2.2 堆的初始化HeapInit

2.3 堆的销毁HeapDestory

2.4 堆的插入HeapPush

​2.4.1 插入代码HeapPush

2.4.2 向上调整代码AdjustUp

2.4.3 交换数据代码Swap

2.5 堆的删除HeapPop

2.5.1 删除代码HeapPop

2.5.2 向下调整算法AdjustDown

2.6 取堆顶的数据HeapTop

2.7 获取堆的数据个数HeapSize

2.8 堆的判空HeapEmpty

三、堆的应用

3.1 堆排序

3.2 TOP-K问题

3.2.1 创建大量数据

3.2.2 求K个最大的元素

3.2.3 验证

四、代码

4.1 堆的代码

4.1.1 Heap.h

4.1.2 Heap.c

4.2 堆排序的代码

4.3 TOP-K的代码


一、堆的概念及结构

堆(Heap)是一种特殊的数据结构,通常以完全二叉树的形式呈现。

堆的核心特性是:

  • 对于大根堆,任意父节点的值都大于或等于其子节点的值
  • 对于小根堆,任意父节点的值都小于或等于其子节点的值

堆通常使用数组来模拟完全二叉树的结构。数组索引按照从上到下、从左到右的方式对应树的节点排列。假设某个节点在数组中的位置为i,则其左子节点和右子节点的位置分别为 2*i+1 2*i+2,而其父节点的位置为(i-1)/2

如下所示:

二、小根堆的实现

2.1 堆的数据结构

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;

2.2 堆的初始化HeapInit

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

2.3 堆的销毁HeapDestory

// 堆的销毁
void HeapDestory(Heap* php) {assert(php);free(php->a);php->capacity = php->size = 0;
}

2.4 堆的插入HeapPush

假如,我们现在有一个数组a:15 18 19 25 28 34 65 49 27 37,他从逻辑上看,是一个小根堆结构,我们将它的逻辑结构画出来如下所示:

我们现在想要将10插入堆里面去,插入10之后,要不允许破坏原本小根堆的结构,所以我们就需要将10一步一步的调整,如下所示:

2.4.1 插入代码HeapPush

// 堆的插入
void HeapPush(Heap* php, HPDataType x) {assert(php);if (php->capacity == php->size) {int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL) {perror("HeapPush()::realloc");exit(1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

2.4.2 向上调整代码AdjustUp

//向上调整,建立大根堆
void AdjustUp(HPDataType* a, int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);}child = parent;parent = (child - 1) / 2;}

2.4.3 交换数据代码Swap

//交换函数
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}

2.5 堆的删除HeapPop

堆的删除,我们首先要确定删除哪一个元素,看上面的数组a:10 15 19 25 18 34 65 49 27 37 28.我们画出他的二叉树表现形式,如下所示,他满足小根堆特性。

 现在数组中有这么多的元素,我们要删除哪一个呢?最常见的是删除第一个元素和最后一个元素,如果我们删除最后一个元素28,删除的没有意义,他既不是最大的也不是最小的,所以堆的删除一般都是删除堆顶元素,也就是以一个元素,删除堆顶元素之后,后面的元素需要向前移动吗?答案是不能,如果向前移动,元素之间的逻辑关系会改变,不满足小堆特性,所有如果我们要删除第一个元素,通常做法是将最后一个元素与第一个元素互换,只有第一个元素不满足小根堆的特性,其他元素都满足,我们还需要写一个向下调整算法。

2.5.1 删除代码HeapPop

// 堆的删除
void HeapPop(Heap* php) {assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, 0, php->size);
}

2.5.2 向下调整算法AdjustDown

void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] < a[child]) {child++;}if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}

2.6 取堆顶的数据HeapTop

// 取堆顶的数据
HPDataType HeapTop(Heap* php) {assert(php);assert(php->size > 0);return php->a[0];
}

2.7 获取堆的数据个数HeapSize

// 堆的数据个数
int HeapSize(Heap* php) {assert(php);return php->size;
}

2.8 堆的判空HeapEmpty

// 堆的判空
int HeapEmpty(Heap* php) {return php->size == 0 ? 1 : 0;
}

三、堆的应用

3.1 堆排序

如果我们想要升序的话,就需要建立大根堆。

如果我们想要降序的话,就需要建立小根堆。

现在我们有一个数组a{ 27,15,19,18,28,34,65,49,25,37 };我们想要将a进行从小到大排序,所以我们就需要对这个数组进行建堆处理。

那现在我们如何建堆呢?

方法一:我们可以访问数组的每一个元素,然后初始化一个堆,将数组的每一个元素插入到堆里面,我们根据堆的自动调整算法,可以自动的变成大根堆,然后我们取出堆顶的元素,把它放在数组里面,然后堆的删除,重复n次。但是这样空间复杂度太高了需要重新新建一个堆。

方法二:我们可以从数组的第二个元素开始,进行向上调整算法,就这个数组变成一个堆,如下所示:

for (int i = 1; i < size; i++) {AdjustUp(a, i);
}

我们打开我们的调试,看到数组a成功的变成了一个大根堆。但是这样时间复杂度太高了。

方法三:可以从最后一个分支节点开始,依次进行向下调整算法,如下所示:

for (int i =(size-2)/2 ; i >= 0; i--)//
{AdjustDown(a, i, size);
}

我们常用的建堆算法是方法三。 

建完堆之后,我们将堆顶元素与最后一个元素互换,然后重新调整堆,重复n次。代码如下所示:

int end = size - 1;
while (end > 0) {Swap(&a[0], &a[end]);AdjustDown(a, 0, end);end--;
}

这样我们就成功的将数组a从小到大排序了。

3.2 TOP-K问题

TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大

比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:

1. 用数据集合中前K个元素来建堆

        前k个最大的元素,则建小堆

        前k个最小的元素,则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素

        将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

3.2.1 创建大量数据

我们使用代码创建大量的数据,如下所示:

void CreatData() {FILE* pf = fopen("data.txt", "w");if (pf == NULL) {perror("fopen");exit(1);}int num = 100000;for (int i = 0; i < num; i++) {int number = rand()+i;fprintf(pf, "%d\n", number);}
}

3.2.2 K个最大的元素

首先,输入k的值,malloc出k个int类型的空间,然后从文件中读取前k个数,将他们放在malloc出来的空间里面,将他们建成小堆,最后依次读取文件中后n-k个,依次与堆顶进行比较,如果大于堆顶就替换,然后调整堆。代码如下:

void TOP_K() {printf("请输入k:");int k = 0;scanf("%d", &k);int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL) {perror("malloc fail");exit(1);}//从文件中拷贝k个数到堆里面FILE* pf = fopen("data.txt", "r");if (pf == NULL) {perror("fopen");exit(1);}for (int i = 0; i < k; i++) {fscanf(pf, "%d", &kminheap[i]);}//建立k个数的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--) {AdjustDown(kminheap, i, k);}//读取剩下的n-k个数据int x = 0;while (fscanf(pf,"%d", &x)>0) {if (x > kminheap[0]) {kminheap[0] = x;AdjustDown(kminheap, 0, k);}}printf("最大的前%d个数", k);for (int i = 0; i < k; i++) {printf("%d ", kminheap[i]);}printf("\n");
}

3.2.3 验证

我们现在已经把最大的前k个输出了,我们如何验证这k个元素就是十万个数据中最大的前10个呢?

我们在创建数据的时候可以%10000000,来控制我们的数据,创建完成数据之后,我们在data.txt文档中随机的修改k个数,在它们后面加上4个0,这样我们就知道k个最大的数后面肯定有4个0。我们调用top-k函数,如下所示:

可以看到最大的10个数后面都带有4个0,说明我们所写的top-k算法没有问题。

四、代码

4.1 堆的代码

4.1.1 Heap.h

#pragma once
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;
void AdjustDown(HPDataType* a, int parent, int size);
void AdjustUp(HPDataType* a, int child);
//交换函数
void Swap(HPDataType* x, HPDataType* y);
void HeapInit(Heap* php);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

4.1.2 Heap.c

#include"Heap.h"
void HeapInit(Heap* php) {assert(php);php->a = NULL;php->capacity = php->size = 0;
}
// 堆的销毁
void HeapDestory(Heap* php) {assert(php);free(php->a);php->capacity = php->size = 0;
}
//交换函数
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}
//向上调整,建立大根堆
void AdjustUp(HPDataType* a, int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);}child = parent;parent = (child - 1) / 2;}
}
// 堆的插入
void HeapPush(Heap* php, HPDataType x) {assert(php);if (php->capacity == php->size) {int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL) {perror("HeapPush()::realloc");exit(1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}
void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] > a[child]) {child++;}if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}
// 堆的删除
void HeapPop(Heap* php) {assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, 0, php->size);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* php) {assert(php);assert(php->size > 0);return php->a[0];
}
// 堆的数据个数
int HeapSize(Heap* php) {assert(php);return php->size;
}
// 堆的判空
int HeapEmpty(Heap* php) {return php->size == 0 ? 1 : 0;
}

4.2 堆排序的代码

//交换函数
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}
//向上调整,建立大根堆
void AdjustUp(HPDataType* a, int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);}child = parent;parent = (child - 1) / 2;}
}
void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] > a[child]) {child++;}if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}
void HeapSort(int* a, int size) {for (int i =(size-2)/2 ; i >= 0; i--)//{AdjustDown(a, i, size);}int end = size - 1;while (end > 0) {Swap(&a[0], &a[end]);AdjustDown(a, 0, end);end--;}
}
int main() {int a[] = { 27,15,19,18,28,34,65,49,25,37 };int size = sizeof(a) / sizeof(a[1]);HeapSort(a, size);for (int i  = 0; i < size; i++) {printf("%d ", a[i]);}return 0;
}

4.3 TOP-K的代码

//交换函数
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}
void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] < a[child]) {child++;}if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}
void CreatData() {FILE* pf = fopen("data.txt", "w");if (pf == NULL) {perror("fopen");exit(1);}int num = 100000;for (int i = 0; i < num; i++) {int number = (rand()+i)%10000000;fprintf(pf, "%d\n", number);}
}
void TOP_K() {printf("请输入k:");int k = 0;scanf("%d", &k);int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL) {perror("malloc fail");exit(1);}//从文件中拷贝k个数到堆里面FILE* pf = fopen("data.txt", "r");if (pf == NULL) {perror("fopen");exit(1);}for (int i = 0; i < k; i++) {fscanf(pf, "%d", &kminheap[i]);}//建立k个数的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--) {AdjustDown(kminheap, i, k);}//读取剩下的n-k个数据int x = 0;while (fscanf(pf,"%d", &x)>0) {if (x > kminheap[0]) {kminheap[0] = x;AdjustDown(kminheap, 0, k);}}printf("最大的前%d个数", k);for (int i = 0; i < k; i++) {printf("%d ", kminheap[i]);}printf("\n");
}
int main() {srand((unsigned int)time(NULL));CreatData();TOP_K();return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

evo轨迹评估工具

文章目录evo参数设置evo_traj指标度量evo_apeevo_rpe结果比较evo工具主要有如下六个常用命令&#xff1a; evo_ape - 用于评估绝对位姿误差&#xff1b;evo_rpe- 用于评估相对位姿误差&#xff1b;evo_traj - 这个主要是用来画轨迹、输出轨迹文件、转换数据格式等功能&#xf…

Django+DRF 实战:自定义异常处理流程

文章目录一、DRF 异常处理流程DRF 默认异常处理流程源码二、实战DRF 自定义异常处理流程应用自定义异常处理流程一、DRF 异常处理流程 DRF 默认异常处理流程 DRF默认的异常处理流程如下&#xff1a; 当异常发生时&#xff0c;会自动调用rest_framework.views.exception_hand…

Spring MVC 1

什么是Spring Web MVC 官方对Spring MVC的描述是这样的&#xff1a;Spring Web MVC 是基于Severlet API构建的原始Web框架&#xff0c;从一开始就包含在Spring框架中。它的正式名称“Spring Web MVC”来自其源模块的名称&#xff08;Spring-webmvc&#xff09;&#xff0c;但它…

一个基于若依(ruoyi-vue3)的小项目部署记录

一、背景 收到朋友的求助&#xff0c;他拿到了一个项目的源代码&#xff0c;说需要我帮助部署。部署要求是需要域名访问。 因为没有文档和其他资料以及帮助&#xff0c;我先清理了源收到的资料&#xff1a; 1.后端&#xff1a;是java代码&#xff0c;一看就是若依框架。心里大大…

【实战总结】WMIC在HW行动中的4类关键应用

WMIC命令完全指南&#xff1a;网络安全运维工程师的深度实践手册 关键词&#xff1a;WMIC命令、Windows管理、网络安全运维、系统信息收集、进程分析、自动化审计 【实战总结】WMIC在HW行动中的4类关键应用 1. 前言 在Windows环境下的网络安全运维中&#xff0c;WMIC&#x…

LKT4304稳定可靠高兼容性国产安全加密芯片

随着 IOT 的飞速发展&#xff0c;智能家居&#xff0c;智能汽车&#xff0c;智能工控等物联网设备和云服务的安全问题成为IOT普及的关键障碍。在设计之初就为物联网产品配备正确的安全解决方案&#xff0c;是帮助预防措施的关键所在。LKT4304是凌科芯安专为物联网应用场景而推出…

Android 网络开发核心知识点

Android 网络开发核心知识点 一、基础网络通信 1. HTTP/HTTPS 协议 HTTP方法&#xff1a;GET、POST、PUT、DELETE等状态码&#xff1a;200(成功)、404(未找到)、500(服务器错误)等HTTPS加密&#xff1a;SSL/TLS握手过程报文结构&#xff1a;请求头/响应头、请求体/响应体 2. 网…

DVWA靶场通关笔记-弱会话IDs(Weak Session IDs Medium级别)

目录 一、Session ID 二、代码审计&#xff08;Medium级别&#xff09; 1、配置security为Medium级别 2、源码分析 &#xff08;1&#xff09;index.php &#xff08;2&#xff09;Medium.php &#xff08;3&#xff09;对比分析 &#xff08;4&#xff09;渗透思路 三…

编辑器Vim的快速入门

如大家所了解的&#xff0c;Vim是一个很古老的编辑器&#xff0c;但是并没有随着时间的流逝消失在编辑器/IDE 的竞争中&#xff0c;Vim 独创的模式机制和 hjkl 移动光标方式使得使用者在编辑文件时可以双手不离开键盘&#xff0c;极大地提升了工作效率。由于 Vim 学习曲线极为陡…

深度学习核心:从基础到前沿的全面解析

&#x1f9e0; 深度学习核心&#xff1a;从基础到前沿的全面解析 &#x1f680; 探索深度学习的核心技术栈&#xff0c;从神经网络基础到最新的Transformer架构 &#x1f4cb; 目录 &#x1f52c; 神经网络基础&#xff1a;从感知机到多层网络&#x1f5bc;️ 卷积神经网络&am…

MySQL索引:数据库的超级目录

MySQL索引&#xff1a;数据库的「超级目录」 想象你有一本1000页的百科全书&#xff0c;要快速找到某个知识点&#xff08;如“光合作用”&#xff09;&#xff1a; ❌ 无索引&#xff1a;逐页翻找 → 全表扫描&#xff08;慢&#xff01;&#xff09;✅ 有索引&#xff1a;直接…

景观桥 涵洞 城门等遮挡物对汽车安全性的影响数学建模和计算方法,需要收集那些数据

对高速公路景观桥影响行车视距的安全问题进行数学建模&#xff0c;需要将物理几何、动力学、概率统计和交通流理论结合起来。以下是分步骤的建模思路和关键模型&#xff1a;一、 核心建模目标 量化视距&#xff08;Sight Distance, SD&#xff09;&#xff1a;计算实际可用视距…

Git 用户名和邮箱配置指南:全局与项目级设置

查看全局配置 git config --global user.name # 查看全局name配置 git config --global user.email # 查看全局email配置 git config --global --list # 查看所有全局配置查看当前项目配置 git config user.name # 查看当前项目name配置 git config user.email # 查看当前项目…

视频序列和射频信号多模态融合算法Fusion-Vital解读

视频序列和射频信号多模态融合算法Fusion-Vital解读概述模型整体流程视频帧时间差分归一化TSM模块视频序列特征融合模块跨模态特征融合模块概述 最近看了Fusion-Vital的视频-射频&#xff08;RGB-RF&#xff09;融合Transformer模型。记录一下&#xff0c;对于实际项目中的多模…

frp内网穿透下创建FTP(解决FTP“服务器回应不可路由的地址。使用服务器地址替代”错误)

使用宝塔面板&#xff0c;点击FTP&#xff0c;下载Pure-FTPd插件 点击Pure-FTPd插件&#xff0c;修改配置文件&#xff0c;找到PassivePortRange, 修改ftp被动端口范围为39000 39003&#xff0c;我们只需要4个被动端口即可&#xff0c;多了不好在内网穿透frp的配置文件中增加…

STM32控制四自由度机械臂(SG90舵机)(硬件篇)(简单易复刻)

1.前期硬件准备 2s锂电池一个&#xff08;用于供电&#xff09;&#xff0c;stm32f103c8t6最小系统板一个&#xff08;主控板&#xff09;&#xff0c;两个摇杆&#xff08;用于摇杆模式&#xff09;&#xff0c;四个电位器&#xff08;用于示教器模式&#xff09;&#xff0c…

华为OD机试_2025 B卷_最差产品奖(Python,100分)(附详细解题思路)

题目描述 A公司准备对他下面的N个产品评选最差奖&#xff0c; 评选的方式是首先对每个产品进行评分&#xff0c;然后根据评分区间计算相邻几个产品中最差的产品。 评选的标准是依次找到从当前产品开始前M个产品中最差的产品&#xff0c;请给出最差产品的评分序列。 输入描述 第…

飞算JavaAI:重塑Java开发效率的智能引擎

飞算JavaAI:重塑Java开发效率的智能引擎 一、飞算JavaAI核心价值 飞算JavaAI是全球首款专注Java语言的智能开发助手,由飞算数智科技(深圳)有限公司研发。它通过AI大模型技术实现: 全流程自动化:从需求分析→软件设计→代码生成一气呵成工程级代码输出:生成包含配置类、…

Java和Go各方面对比:现代编程语言的深度分析

Java和Go各方面对比&#xff1a;现代编程语言的深度分析 引言 在当今的软件开发领域&#xff0c;选择合适的编程语言对项目的成功至关重要。Java作为一门成熟的面向对象语言&#xff0c;已经在企业级开发中占据主导地位超过25年。而Go&#xff08;Golang&#xff09;作为Google…

CloudCanal:一款企业级实时数据同步、迁移工具

CloudCanal 是一款可视化的数据同步、迁移工具&#xff0c;可以帮助企业构建高质量数据管道&#xff0c;具备实时高效、精确互联、稳定可拓展、一站式、混合部署、复杂数据转换等优点。 应用场景 CloudCanal 可以帮助企业实现以下数据应用场景&#xff1a; 数据同步&#xff…