【C语言】数据结构——小堆实例探究

这篇具有很好参考价值的文章主要介绍了【C语言】数据结构——小堆实例探究。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

💗个人主页💗
⭐个人专栏——数据结构学习⭐
💫点击关注🤩一起学习C语言💯💫

导读:

我们在前面学习了单链表和顺序表,以及栈和队列。
今天我们来学习小堆。
关注博主或是订阅专栏,掌握第一消息。

1. 堆的概念及结构

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段。

1.1 什么是堆

堆是一种特殊的数据结构,它可以看做是一个完全二叉树(或者近似二叉树),其中每个节点的值都大于等于(或小于等于)其子节点的值。在一个最大堆中,根节点的值是最大的;在一个最小堆中,根节点的值是最小的。
【C语言】数据结构——小堆实例探究,数据结构学习,c语言,开发语言,数据结构

1.2 堆的特点

堆的主要特点是:每个节点的值都大于等于(或小于等于)其子节点的值。这种特点使得堆可以快速找到最大(或最小)的元素。另外,堆还可以用于排序和优先队列等应用。
堆中兄弟节点的值之间没有关联。在堆中,节点之间的关系仅由其在树中的位置决定。

1.3 堆的结构

堆通常使用数组来实现,数组的下标代表节点在堆中的位置。根据节点在数组中的位置,可以通过简单的计算得到其父节点、左子节点和右子节点的位置。这样,在堆中插入一个新元素、删除堆顶的元素或者调整堆的结构时,只需要对数组进行简单的操作,而不需要改变整个堆的结构。

2. 堆的实现

我们需要创建两个 C文件: study.c 和 Heap.c,以及一个 头文件: Heap.h。

头文件来声明函数,一个C文件来定义函数,另外一个C文件来用于主函数main()进行测试。

堆的常见操作包括插入元素、删除堆顶元素、堆化(调整堆的结构使其满足堆的特点)等。其中,插入元素和删除堆顶元素的时间复杂度为O(logn),堆化的时间复杂度为O(nlogn)。

3. 代码实现

3.1 定义结构体

Heap.h:

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;		//记录数组内的有效数据
	int capacity;	//记录数组空间大小
}HP;

3.2 堆的初始化

Heap.h:

//堆的初始化
void HeapInit(HP* php);

Heap.c:

//堆的初始化
void HeapInit(HP* php)
{
	//各值初始化为0
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

3.3 堆的销毁

我们的数组空间是用malloc函数开辟的,使用完之后需要进行释放。
Heap.h:

// 堆的销毁
void HeapDestroy(HP* php);

Heap.c:

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

3.4 向上调整父节点与子节点

在出入数组后,我们需要对数组进行调整,以实现堆的结构特点。
在数组中,下标*2+1就是他的子节点,同样的下标-1/2就是他的父节点。
Heap.h:

//向上调整父节点与子节点
void AdjustUp(HPDataType* a, int child);

Heap.c:

//交换父节点和子节点的值
void Swap(int* x, int* y)
{
	int 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;
		}
		else
		{
			break;
		}
	}
}

【C语言】数据结构——小堆实例探究,数据结构学习,c语言,开发语言,数据结构

3.5 堆的插入

Heap.h:

// 堆的插入
void HeapPush(HP* php, HPDataType x);

Heap.c:

// 堆的插入
// 堆的插入
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//首先检查数组容量是否足够
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	//在插入数值后需要检查是否要进行调整
	AdjustUp(php->a, php->size);
	php->size++;
}

【C语言】数据结构——小堆实例探究,数据结构学习,c语言,开发语言,数据结构
【C语言】数据结构——小堆实例探究,数据结构学习,c语言,开发语言,数据结构

3.6 向下调整父节点与子节点

删除堆是删除堆顶的数据,但是我们无法直接删除第一个元素,这有极大的可能会使我们的堆崩溃,不再具有堆的特点,而在删除之后把其它数值都往前移动,再进行调整是一项很大的工作量。
所以我们可以将堆顶的数据根最后一个数据一换,然后删除数组最后一个数据,再进行向下调整算法。将当前的根数值调整到符合堆特点的位置去。
Heap.h:

//向下调整父节点与子节点
void AdjustDown(int* a, int size, int parent);

Heap.c:

//向下调整父节点与子节点
void AdjustDown(int* a, int size, int parent)
{
	assert(a);
	int child = parent * 2 + 1;//找到孩子节点
	while (child < size)
	{
		//找孩子中较小的一个
		if ((a[child] > a[child + 1]) && (child + 1) < size)
		{
			child += 1;
		}
		//判断两个大小进行交换
		if (a[parent] > a[child])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

3.7 堆的删除

Heap.h:

// 堆的删除
void HeapPop(HP* php);

Heap.c:

// 堆的删除
void HeapPop(HP* php)
{
	assert(php);
	//先检查数组是否有可删除的数据
	assert(php->size > 0);
	//交换首尾元素
	Swap(&php->a[php->size - 1], &php->a[0]);
	php->size--;
	//向下进行调整
	AdjustDown(php->a, php->size, 0);

}

【C语言】数据结构——小堆实例探究,数据结构学习,c语言,开发语言,数据结构
【C语言】数据结构——小堆实例探究,数据结构学习,c语言,开发语言,数据结构

3.8 获取堆顶元素

返回数组首元素即可
Heap.h:

// 取堆顶的数据
HPDataType HeapTop(HP* php);

Heap.c:

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

3.9 获取堆的个数

直接返回size的值即可
Heap.h:

// 堆的数据个数
size_t HeapSize(HP* php);

Heap.c:

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

3.10 堆的判空

只需判断size的值是否为0,如果是,返回true,反之返回false。
Heap.h:

// 堆的判空
bool HeapEmpty(HP* php);

Heap.c:

// 堆的判空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

4. 代码整理

4.1 Heap.h

#define _CRT_SECURE_NO_WARNINGS 
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;		//记录数组内的有效数据
	int capacity;	//记录数组空间大小
}HP;

//堆的初始化
void HeapInit(HP* php);

// 堆的销毁
void HeapDestroy(HP* php);

// 堆的插入
void HeapPush(HP* php, HPDataType x);

// 堆的删除
void HeapPop(HP* php);

// 取堆顶的数据
HPDataType HeapTop(HP* php);

// 堆的数据个数
size_t HeapSize(HP* php);

// 堆的判空
bool HeapEmpty(HP* php);

//向上调整父节点与子节点
void AdjustUp(HPDataType* a, int child);

//向下调整父节点与子节点
void AdjustDown(int* a, int size, int parent);

//交换父节点和子节点的值
void Swap(int* child, int* parent);

4.2 Heap.c

#include "Heap.h"

//堆的初始化
void HeapInit(HP* php)
{
	//各值初始化为0
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

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

//交换父节点和子节点的值
void Swap(int* x, int* y)
{
	int 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;
		}
		else
		{
			break;
		}
	}
}
// 堆的插入
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//首先检查数组容量是否足够
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	//在插入数值后需要检查是否要进行调整
	AdjustUp(php->a, php->size);
	php->size++;
}


//向下调整父节点与子节点
void AdjustDown(int* a, int size, int parent)
{
	assert(a);
	int child = parent * 2 + 1;//找到孩子节点
	while (child < size)
	{
		//找孩子中较小的一个
		if ((a[child] > a[child + 1]) && (child + 1) < size)
		{
			child += 1;
		}
		//判断两个大小进行交换
		if (a[parent] > a[child])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

// 堆的删除
void HeapPop(HP* php)
{
	assert(php);
	//先检查数组是否有可删除的数据
	assert(php->size > 0);
	//交换首尾元素
	Swap(&php->a[php->size - 1], &php->a[0]);
	php->size--;
	//向下进行调整
	AdjustDown(php->a, php->size, 0);

}

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

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

// 堆的判空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

4.3 study.c

void Test1()
{
	int array[] = { 27,15,19,18,28,34,65,49,25,37 };
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(array) / sizeof(int); i++)
	{
		HeapPush(&hp, array[i]);//插入数据
	}
	int k = HeapSize(&hp);
	while (k--)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}


int main()
{;
	Test1();
	return 0;
}

【C语言】数据结构——小堆实例探究,数据结构学习,c语言,开发语言,数据结构文章来源地址https://www.toymoban.com/news/detail-762343.html

到了这里,关于【C语言】数据结构——小堆实例探究的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)

    目录 问题描述  解题思路 伪代码  总体算法 DFS算法 伪代码解读 总体算法 DFS算法 具体实现(C语言) 在老电影“007之生死关头”(Live and Let Die)中有一个情节,007被毒贩抓到一个鳄鱼池中心的小岛上,他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑

    2024年02月05日
    浏览(78)
  • C语言数据结构——图的最短路径算法解决实例问题

    一、问题描述 W公司在某个地区有6个产品销售点,现根据业务需要打算在其中某个销售点上建立一个中心仓库,负责向其他销售点提供产品。由于运输线路不同,运输费用也不同。假定每天需要向每个销售点运输一次产品,那么应将中心仓库建在哪个销售点上,才能使运输费

    2024年02月08日
    浏览(48)
  • 【数据结构】从数据结构角度深入探究队列

    队列是计算机科学中的一种基本数据结构,用于存储和管理数据。在计算机程序中,队列被广泛应用于任务调度、进程管理等场景。本文将介绍队列的概念、特点、常见操作以及应用。 你们在用电脑时有没有经历过,机器有时会处于疑似死机的状态,鼠标点什么似乎都没用,

    2024年02月06日
    浏览(40)
  • 【学习笔记】数据结构算法文档(类C语言)

    1.1.1 线性表的顺序存储表示 1.1.2 顺序表中基本操作的实现 1.1.2.1 初始化 1.1.2.2 取值 1.1.2.3 查找 1.1.2.4 插入 1.1.2.5 删除 1.1.2.6 计数 1.2.1 单链表的定义和表示 ★ 关于结点 1.2.2 单链表基本操作的实现 1.2.2.1 初始化 1.2.2.2 取值 1.2.2.3 查找 1.2.2.4 插入 1.2.2.5 删除 1.2.2.6 前插法创建单

    2024年02月07日
    浏览(44)
  • 【海贼王的数据航海:利用数据结构成为数据海洋的霸主】探究二叉树的奥秘

    目录 1 - 树的概念及结构 1.1 - 树的概念 1.2 - 树的相关概念 1.3 - 树的表示 1.4 - 树在实际中的运用(表示文件系统的目录树结构) 2 - 二叉树概念及结构 2.1 - 二叉树的概念 2.2 - 现实中的二叉树 2.3 - 特殊的二叉树 2.4 - 二叉树的性质 2.5 - 二叉树的存储结构 3 - 二叉树的顺序结构及实

    2024年03月12日
    浏览(58)
  • 数据结构学习——C语言对栈的基本操作

             栈(Stack)是一种常用的数据结构,遵循先进后出(LIFO)的原则,对表尾进行操作,常用于临时存储和撤销等操作,其基本操作包括栈的创建、入栈(也叫压栈Push)、出栈(又称弹栈)、栈的遍历、栈的清空(clear)、栈的销毁(destroy)等。         栈的创建有两种方式,一种是通

    2024年02月07日
    浏览(58)
  • 数据结构(c++语言版) 邓俊辉 第五章:二叉树学习笔记

    5.1二叉树及其表示         树是由节点和边组成的。 1.有根树         树是由顶点(vertex)和边(edge)组成。树的每个顶点也叫节点(node)。 2.深度与层次         由树的连通性,每一节点与根都有一条路径相连:根据树的无环性,由根通往每个节点的路径必然唯一。  

    2024年02月13日
    浏览(46)
  • 【C++】引用之带你“消除”C语言版数据结构教材的一些困惑(虽然是C++的内容,但是强烈建议正在学习数据结构的同学点进来看看)

    👀樊梓慕: 个人主页  🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 引用的概念 引用的特性 引用的使用场景 引用和指针的区别 C语言版数据结构教材的解惑 不知道

    2024年02月08日
    浏览(46)
  • AAC 音频数据结构实例分析:

    AAC 音频数据结构实例分析: AAC 有两种数据交换格式:ADTS 和 ADIF ADIF: Audio Data Interchange Format, 一个文件只有一个头,可类比dvd中使用的ps流。 ADTS:Audio Data Transport Stream, 每个frame中都有这个同步头, 可类比dvb中的ts流. 本博客只介绍 ADTS 格式AAC 基本构成是7bytes 头部+原始数据. 循

    2024年02月02日
    浏览(35)
  • 数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)

    目录 题目描述 输入示例 输出示例 解题思路  解题方法(C语言) 解析 有序的二叉树遍历可以用堆栈以非递归的方式实现。 例如: 假设遍历一个节点数为6的二叉树(节点数据分别为1到6)时, 堆栈操作为:push(1);push(2);push(3);pop();pop();push(4);pop()

    2024年02月07日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包