数据结构——堆（C语言实现）

文章目录

  • 什么是堆
  • 堆的实现
    • 堆的结构定义
    • 堆的初始化接口
    • 堆的销毁接口
    • 堆的插入数据接口
    • 向上调整建堆接口
    • 判断堆是否为空
    • 堆的删除数据接口
    • 向下调整建堆接口
    • 获取堆顶数据
    • 获取堆的有效数据个数
    • 完整实现代码
    • 小结
  • 堆排序
    • 堆排序的实现
  • 关于建堆和堆排序时间复杂度的分析
    • 向下调整建堆
    • 向上调整建堆
    • 堆排序
    • 小结
  • TOPK问题的介绍

什么是堆

堆是一种特殊的数据结构，它是一棵完全二叉树，同时满足堆属性，即父节点的值总是大于或小于其子节点的值。如果父节点的值总是大于子节点的值，那么我们称之为大根堆；反之，如果父节点的值总是小于子节点的值，那么我们称之为小根堆。在堆中，根节点的值最大（大根堆）或最小（小根堆），因此它也被称为堆顶。堆经常用于排序、topK问题等场景。
在这里插入图片描述

堆的实现

本篇文章使用c语言实现并以头文件和源文件分离的形式，也会逐步介绍各个接口的实现思路以及提供参考代码。

堆的结构定义

堆的结构定义其实是一个特殊的顺序表，这点和栈类似。所以，需要用一个指针指向动态开辟的内存，需要一个指向当前下标位置的变量，以及需要一个记录当前动态内存的容量。
在这里插入图片描述

堆的初始化接口

堆初始化接口实现思路如下，首先，改变一个堆，我们需要传它的地址。所以参数部分需要写成Hp*。在接口的一开始先判断指针的合法性。然后开辟动态内存，判断一下动态内存的有效性。最后，初始化结构体成员即可。
在这里插入图片描述

堆的销毁接口

释放动态申请的空间，free后及时置空的好习惯是我们应该要养成的。最后将size和capacity置零即可。
在这里插入图片描述

堆的插入数据接口

堆的插入接口实现思路如下，assert判断指针有效性，这是一个好的编程习惯，建议大家平时也养成这种习惯。首先判断容量是否满了，满了的话就扩容。然后直接下面的插入数据逻辑，其实就是类似于顺序表。直接将数据插入size下标的位置，++size即可。最后调用向上调整建堆接口，使堆的结构不变。
在这里插入图片描述

向上调整建堆接口

首先要根据孩子的下标位置，推断出父节点的下标位置。然后开始向上调整，向上调整的过程是一个循环的过程，循环的迭代条件就是当child大于根节点下标就继续支持循环。当子节点小于父节点循环终止。若父节点小于子节点那么进行对应下标的数据交换，然后迭代子节点下标和父节点下标即可。
在这里插入图片描述

在这里插入图片描述

判断堆是否为空

判断堆是否为空接口思路相对简单，类似于顺序表的判空思路，当下一个可以插入数据的下标为0时，表示为空堆。
在这里插入图片描述

堆的删除数据接口

要删除堆的数据，是删除堆的堆顶数据还是堆底数据呢？答案是删除堆顶的数据，因为删除堆底的数据没有什么价值。而删除堆顶可以产生一些价值，如排序或者对一些前排名K个的数据进行收集等。举个例子，当我们在购物app想选一个电脑，我们可以按照销量进行排序这也是堆应用的一个场景。回到正题，删除堆顶的实现思路如下，我们让堆顶数据和最后一个数据交换，然后让size–，达到删除堆顶数据的效果，并且大大提升了效率。最后向下调整建堆即可。
在这里插入图片描述

在这里插入图片描述

向下调整建堆接口

向下调整建堆实现思路如下，首先，向下调整的过程是一个循环，它的终止条件为parent > size。循环体内部就是向下调整的核心思路，parent跟左右孩子较大的（较小的）比，本文以实现大堆为例。这里要介绍一个比较重要的概念，由于堆的底层使用顺序表存储，所以同一个父亲的左孩子右孩子是相邻存储的。即左孩子下标+1就是右孩子下标。让父亲和左右孩子较大的那一个比较，如果父亲小于孩子就交换位置，然后迭代。注意：向下调整的条件是左右子树必须是堆。
在这里插入图片描述

获取堆顶数据

其实，就是访问顺序表的第一个元素。但是，这样提供一个接口是非常符合接口的一致性以及对于代码的可读性有极大的提升的。
在这里插入图片描述

获取堆的有效数据个数

由于我们的size是从0开始，所以直接return size即可。
在这里插入图片描述

完整实现代码

//Heap.h文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//默认起始容量
#define DefaultCapacity 4

//存储的数据类型
typedef int HpDataType;

typedef struct Heap
{
	HpDataType* data;
	int size;//可以插入数据的下标
	int capacity;//容量
}Hp;


//初始化
void HpInit(Hp* pHp);

//堆的销毁
void HpDestroy(Hp* pHp);

//插入数据
void HpPush(Hp* pHp, HpDataType x);

//向上调整建堆
void AdjustUp(HpDataType* data, int child);

//判断是否为空
bool HpEmpty(Hp* pHp);

//删除数据
void HpPop(Hp* pHp);

//向下调整建堆
void AdjustDown(HpDataType* data,int size, int parent);

// 取堆顶的数据
HpDataType HpTop(Hp* pHp);

// 堆的数据个数
int HpSize(Hp* pHp);

// Heap.c文件
#include"Heap.h"

//初始化
void HpInit(Hp* pHp) 
{
	//判断合法性
	assert(pHp);

	//开辟动态空间
	HpDataType* tmp = (HpDataType*)malloc(sizeof(HpDataType) * DefaultCapacity);
	if (tmp == NULL)//判断合法性
	{
		perror("malloc fail");
		return;
	}

	//初始化
	pHp->data = tmp;
	pHp->size = 0;
	pHp->capacity = DefaultCapacity;
}

//堆的销毁
void HpDestroy(Hp* pHp)
{
	//判断合法性
	assert(pHp);

	//释放内存和清理
	free(pHp->data);
	pHp->data = NULL;
	pHp->size = pHp->capacity = 0;

}


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

//向上调整建堆
void AdjustUp(HpDataType* data, int child)
{
	//判断指针有效性
	assert(data);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		//向上调整呢
		if (data[child] > data[parent])
		{
			Swap(&data[child], &data[parent]);
		}
		else
		{
			break;
		}	
		//迭代
		child = parent;
		parent = (child - 1) / 2;
	}

}

//插入数据
void HpPush(Hp* pHp, HpDataType x)
{
	//判断指针有效性
	assert(pHp);

	//判断容量是否满了
	if (pHp->size == pHp->capacity)
	{
		HpDataType* tmp = (HpDataType*)realloc(pHp->data,sizeof(HpDataType) * pHp->capacity * 2);
		if (tmp == NULL)//判断空间合法性
		{
			perror("malloc fail");
			return;
		}
		//扩容后
		pHp->data = tmp;
		pHp->capacity *= 2;
	}

	//数据入堆
	pHp->data[pHp->size] = x;
	pHp->size++;

	//向上调整建堆
	AdjustUp(pHp->data, pHp->size - 1);

}
void AdjustDown(HpDataType* data, int size, int parent)
{
	//断言检查
	assert(data);

	int child = parent * 2 + 1;

	while (child < size)
	{
		//求出左右孩子较大的那个下标
		if (child + 1 < size && data[child + 1] > data[child])
		{
			child++;
		}
		//父亲比孩子小就交换位置
		if (data[child] > data[parent])
		{
			//交换
			Swap(&data[child], &data[parent]);
			//迭代
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}

void HpPop(Hp* pHp)
{
	//断言检查
	assert(pHp);

	//删除数据
	Swap(&pHp->data[0], &pHp->data[pHp->size-1]);
	pHp->size--;

	//向下调整建堆
	AdjustDown(pHp->data,pHp->size-1,0);

}

//判断是否为空
bool HpEmpty(Hp* pHp)
{
	assert(pHp);
	
	return pHp->size == 0;
}

// 取堆顶的数据
HpDataType HpTop(Hp* pHp)
{
	assert(pHp);

	return pHp->data[0];
}

// 堆的数据个数
int HpSize(Hp* pHp)
{
	assert(pHp);

	return pHp->size;
}

小结

操作堆这种数据结构就像吃老婆饼，你吃的是香甜的饼，至于是不是你老婆做的那就不一定了。但是，你在吃的时候想像成你老婆做的饼吃起来也别有一番风味。堆在逻辑结构上你操作的是一颗树，在底层的存储上又是一个顺序表。这就比较抽象的地方，需要考验我们画图以及走读代码调试的能力。

堆排序

堆排序其实就是堆这个数据结构的一种常见的使用方式。堆排序的核心思想就是利用堆删除的思想来进行排序操作。堆排序是一种时间复杂度O(N*logN)的不稳定排序。至于排序的稳定性的讲解在后面的博客会给大家介绍。

堆排序的实现

堆排序的实现思路如下，首先确定排序的顺序并将数据建成堆，升序建大堆，降序建小堆。建堆的话建议使用向下调整建堆。因为时间复杂度为O(logN)，若使用向上调整建堆，那么时间复杂度为O(N*logN)。这样的时间复杂度对于找出堆顶数据的损耗太大，还不如直接遍历一遍（时间复杂度）。
在这里插入图片描述

接着是利用堆删除的思想进行排序。下面就以排升序为例。
在这里插入图片描述

//堆排序--排升序建大堆
void HeapSort(int* arr, int n)
{
	//向下建堆，效率更高
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(arr,n-1,i);
	}

	//排序
	//利用堆删除的思想进行排序
	int end = n - 1;
	while (end > 0)
	{
		//交换
		int tmp = arr[0];
		arr[0] = arr[end];
		arr[end] = tmp;
		//调整堆
		AdjustDown(arr, end-1, 0);
		end--;
	}
}

关于建堆和堆排序时间复杂度的分析

向下调整建堆

在前面的堆排序实现中，提到向下调整建堆的效率更高，这是因为向下调整建堆的时间复杂度是O(N)。下面我就带领大家简单分析一下向下调整建堆的时间复杂度。
在这里插入图片描述

向上调整建堆

向上调整建堆的时间复杂度为O(N*logN)。下面请看向上调整的时间复杂度问题。
在这里插入图片描述

堆排序

堆排序的时间复杂度为O(NlogN)。向下调整建堆的复杂度为O(N)，这个上面已经分析。排序部分的话结合从第一个非叶子结点开始向下调整堆的话是O(NlogN)。
·

小结

上面介绍的建堆时间复杂度和堆排序复杂度，记个结论其实就可以了。当然，从实现的角度上也不难分析出向上调整建堆和向下调整建堆的大致效率上的差距。因为向下调整从第一个非叶子结点开始调整，最坏的情况下也要比向上调整少调整一半的结点。这在效率上已经胜出不少了。

TOPK问题的介绍

TOPK问题是指在一组数据中，找出前K个最大或最小的数据的问题，常见的解决方法包括堆排序、快速排序、归并排序等。该问题在数据分析、机器学习等领域中经常出现。当然有一种特殊场景下用堆进行TOK的筛选非常的妙。假设现在有100亿个整数，要求出前50个数，我们可以建一个小堆，只要遍历的数据比堆顶数据大就替代它进堆（向下调整），最终就可以得到最大的前五十个数。下面用一个样例简单感受一下。

void AdjustDownSH(HpDataType* data, int size, int parent)
{
	//断言检查
	assert(data);

	int child = parent * 2 + 1;

	while (child < size)
	{
		//求出左右孩子较大的那个下标
		if (child + 1 < size && data[child + 1] < data[child])
		{
			child++;
		}
		//父亲比孩子小就交换位置
		if (data[child] < data[parent])
		{
			//交换
			Swap(&data[child], &data[parent]);
			//迭代
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}

void PrintTopK(const char* file, int k)
{
	// 1. 建堆--用a中前k个元素建小堆
	int* topk = (int*)malloc(sizeof(int) * k);
	assert(topk);

	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}

	// 读出前k个数据建小堆
	for (int i = 0; i < k; ++i)
	{
		fscanf(fout, "%d", &topk[i]);
	}

	for (int i = (k - 2) / 2; i >= 0; --i)
	{
		AdjustDownSH(topk, k, i);
	}

	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	int val = 0;
	int ret = fscanf(fout, "%d", &val);
	while (ret != EOF)
	{
		if (val > topk[0])
		{
			topk[0] = val;
			AdjustDownSH(topk, k, 0);
		}

		ret = fscanf(fout, "%d", &val);
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", topk[i]);
	}
	printf("\n");

	free(topk);
	fclose(fout);
}

void CreateNDate()
{
	// 造数据
	int n = 10000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (size_t i = 0; i < n; ++i)
	{
		int x = rand() % 10000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

int main()
{
	CreateNDate();
	PrintTopK("data.txt", 10);

	return 0;
}

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

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

相关文章

day52|动态规划13-子序列问题

day52|动态规划13-子序列问题

子序列系列问题 300.最长递增子序列 什么是递增子序列&#xff1a; 元素之间可以不连续&#xff0c;但是需要保证他们所在位置是元素在数组中的原始位置。 dp数组dp[i]表示以nums[i]为结尾的最长递增子序列的长度。递归函数&#xff1a;dp[i] max(dp[j]1,dp[j])初始化条件&…
阅读更多...
算法刷题-链表-移除链表元素

算法刷题-链表-移除链表元素

链表操作中&#xff0c;可以使用原链表来直接进行删除操作&#xff0c;也可以设置一个虚拟头结点再进行删除操作&#xff0c;接下来看一看哪种方式更方便。 203.移除链表元素 力扣题目链接 题意&#xff1a;删除链表中等于给定值 val 的所有节点。 示例 1&#xff1a; 输入&…
阅读更多...
Linux下信号量使用总结

Linux下信号量使用总结

目录 1.Linux下信号量简介 2.POSIX信号量 2.1 无名信号量 2.2 有名信号量 3.System V信号量 1.Linux下信号量简介 信号量是解决进程之间的同步与互斥的IPC机制&#xff0c;互斥与同步关系存在的症结在于临界资源。 临界资源是在同一个时刻只容许有限个&#xff08;一般只有…
阅读更多...
【数据结构与算法】03 队列（顺序队列--循环队列--优先级队列--链队列）

【数据结构与算法】03 队列（顺序队列--循环队列--优先级队列--链队列）

一、概念1.1 队列的基本概念1.2 队列的顺序存储结构1.21 顺序队列&#xff08;静态队列&#xff09;1.22 循环队列1.23 优先级队列 1.3 队列的链式存储结构 二、C语言实现2.1 顺序存储2.11 顺序队列2.12 循环队列2.13 优先级队列 2.2 链式存储 一、概念 1.1 队列的基本概念 队…
阅读更多...
Linux内核中断和Linux内核定时器

Linux内核中断和Linux内核定时器

目录 Linux内核中断 Linux内核定时器 Linux内核中断 int request_irq(unsigned int irq, irq_handler_t handler, unsigned long flags,const char *name, void *dev) 功能&#xff1a;注册中断 参数&#xff1a; irq : 软中断号 gpio的软中断号 软中断号 gpio_to_i…
阅读更多...
【PCB专题】案例：绕等长怎么直接以颜色区分看出是否绕好

【PCB专题】案例：绕等长怎么直接以颜色区分看出是否绕好

PCB上对于时序的处理，在板卡上实际我们是通过绕等长的手段。做为一个合格的Layout工程师，等长的处理是不可或缺的技能。 一般来说，在绕等长的时候我们可以使用Delay Tune命令来改变走线的长度，然后通过规则管理器中分析看看哪根线长哪根线短。 但是在实际工作中，很可能绕着…
阅读更多...
Android应用程序进程的启动过程

Android应用程序进程的启动过程

Android应用程序进程的启动过程 导语 到这篇文章为止&#xff0c;我们已经简要地了解过了Android系统的启动流程了&#xff0c;其中比较重要的内容有Zygote进程的启动和SystemService以及Launcher的启动&#xff0c;接下来我们将要学习的是Android应用程序的启动过程&#xff…
阅读更多...
华为OD机试真题 JavaScript 实现【最多几个直角三角形】【2023Q1 100分】

华为OD机试真题 JavaScript 实现【最多几个直角三角形】【2023Q1 100分】

一、题目描述 有 N 条线段&#xff0c;长度分别为 a[1]-a[n]。 现要求你计算这 N 条线段最多可以组合成几个直角三角形&#xff0c;每条线段只能使用一次&#xff0c;每个三角形包含三条线段。 二、输入描述 第一行输入一个正整数 T (1< T< 100) &#xff0c;表示有…
阅读更多...
2023蓝桥杯大学A组C++决赛游记+个人题解

2023蓝桥杯大学A组C++决赛游记+个人题解

Day0 发烧了一晚上没睡着&#xff0c;感觉鼻子被打火机烧烤一样难受&#xff0c;心情烦躁 早上6点起来吃了个早饭&#xff0c;思考能力完全丧失了&#xff0c;开始看此花亭奇谭 看了六集&#xff0c;准备复习数据结构考试&#xff0c;然后秒睡 一睁眼就是下午2点了 挂了个…
阅读更多...
springboot项目外卖管理 day05-新增与删除套餐

springboot项目外卖管理 day05-新增与删除套餐

文章目录 一、新增菜品1.1、需求分析1.2、数据模型setmealsetmeal_dish 1.3、代码开发-梳理交互过程1.3.1、下拉框展示1.3.2、菜品窗口展示1.3.3、新增套餐 2、套餐分页查询 一、新增菜品 1.1、需求分析 套餐就是菜品的集合。 后台系统中可以管理套餐信息&#xff0c;通过新…
阅读更多...
一文打通：从字节码指令的角度解读前置后置自增自减（加加++减减--）

一文打通：从字节码指令的角度解读前置后置自增自减（加加++减减--）

文章目录 1.前置了解的知识1.1 栈这种数据结构1.2 局部变量表和操作数栈1.3 三个字节码指令 2.单独使用后置与前置2.1 后置字节码指令2.2 前置字节码指令2.3 总结 3.需要返回值的情况下使用后置与前置3.1 后置字节码指令3.2 前置字节码指令3.3 总结3.4 练习&#x1f340; 练习一…
阅读更多...
了解ASEMI代理英飞凌TLE6208-6G其功能和应用的综合指南

了解ASEMI代理英飞凌TLE6208-6G其功能和应用的综合指南

编辑-Z TLE6208-6G是一款高度集成、通用且高效的汽车半桥驱动器&#xff0c;由英飞凌设计。这种功能强大的设备专门设计用于满足汽车应用的苛刻要求&#xff0c;如控制直流电机、螺线管和电阻负载。在本文中&#xff0c;我们将深入研究TLE6208-6G的功能、优点和应用&#xff0…
阅读更多...
实现表白墙

实现表白墙

我们已经学习了Http以及Servlet类的相关知识 今天我们来实操一下,实现一个简单的既有前端又有后端的网站–表白墙 之前在学习前端的时候已经写过了表白墙的前端代码,存在两个问题 1.页面重启,数据丢失 2.数据只是在本地的,别人看不见 那么这样的问题我们要咋样解决呢? 引入…
阅读更多...
（七）CSharp-CSharp图解教程版-事件

（七）CSharp-CSharp图解教程版-事件

一、发布者和订阅者 发布者/订阅者模式&#xff08;publish/subscriber pattern&#xff09;&#xff1a; 很多程序都有一个共同的需求&#xff0c;即当一个特定的程序事件发生时&#xff0c;程序的其他部分可以得到该事件已经发生的通知。 发布者&#xff1a; 发布者类定义…
阅读更多...
Excel函数VLOOKUP常用方法

Excel函数VLOOKUP常用方法

一、基础用法 1、精确匹配 公式&#xff1a;VLOOKUP(待匹配值&#xff0c;查找范围&#xff0c;范围列数&#xff0c;查找方式) 定义好要输出表的表头和第一列&#xff0c;第一列即为要查找和匹配的父内容&#xff0c;在第二列输入公式&#xff0c;被查找表中一定也要将待查…
阅读更多...
基于SPAD / SiPM技术的激光雷达方案

基于SPAD / SiPM技术的激光雷达方案

激光雷达(LiDAR)是一种测距技术&#xff0c;近年来越来越多地用于汽车先进驾驶辅助系统(ADAS)、手势识别和3D映射等应用。尤其在汽车领域&#xff0c;随着传感器融合的趋势&#xff0c;LiDAR结合成像、超声波、毫米波雷达&#xff0c;互为补足&#xff0c;为汽车提供全方位感知…
阅读更多...
【力扣刷题 | 第六天】

【力扣刷题 | 第六天】

目录 前言&#xff1a; 344. 反转字符串 - 力扣&#xff08;LeetCode&#xff09; 541. 反转字符串 II - 力扣&#xff08;LeetCode&#xff09; 今天我们进入字符串章节的刷题旅程&#xff0c;希望各位小伙伴可以和我一起坚持下去&#xff0c;一起征服力扣&#xff01; 前言…
阅读更多...
前端前端学习不断

前端前端学习不断

卷吧卷吧...&#xff0c;这东西什么时候是个头啊……
阅读更多...
半导体器件基础（期末模电速成）

半导体器件基础（期末模电速成）

目录 1、半导体分类 2、PN结 3、二极管 4、稳压二极管 5、三极管 6、场效应管 1、半导体分类 2、PN结 3、二极管 伏安特性&#xff1a; 我们第七版模电书上给的正向导通压降分别约为0.7和0.2V&#xff0c;且硅的单向导电性更好 如何确定二极管状态&#xff1f; 阳极电压…
阅读更多...
怎么快速掌握Python爬虫技术？

怎么快速掌握Python爬虫技术？

Python总的来说是一门比较容易入门的编程语言&#xff0c;因为它的语法简洁易懂&#xff0c;而且有很多优秀的教程和资源可供学习。相比其他编程语言&#xff0c;Python 的学习曲线较为平缓&#xff0c;初学者可以很快上手&#xff0c;但要想深入掌握 Python&#xff0c;还需要…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站