数据结构——堆(Heap)功能的实现

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

一、堆的基本概念

什么是堆?

  简单来说,堆就是一个完全二叉树,在这个完全二叉树中,每一个子树的根节点总是大于它的左右孩子,那就称为大堆,反过来,每一个子树的根节点总是小于它的左右孩子,那就称为小堆。

堆的性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。

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

  小堆的顺序存储结构与完全二叉树逻辑结构:

数据结构——堆(Heap)功能的实现,数据结构,算法,c语言  大堆的顺序存储结构与完全二叉树逻辑结构:数据结构——堆(Heap)功能的实现,数据结构,算法,c语言

二、堆的功能实现

一、创建工程

数据结构——堆(Heap)功能的实现,数据结构,算法,c语言

创建好工程后,新建头文件Heap.h,源文件Heap.c、main.c

头文件Heap.h包含我们代码所需的头文件,还有结构体、函数的声明。

源文件Heap.c包含我们堆功能函数的实现。

源文件main.c包含我们运用堆的源代码。

二、功能函数实现

上面已经所说,堆是顺序结构存储,所以这里结构体的定义和顺序表相同

下面呈上头文件中结构体的定义与函数的声明

#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 InitHeap(HP* php);
//销毁函数
void DestroyHeap(HP* php);
//建堆函数
void PushHeap(HP* php,HPDataType x);
//删除根节点函数
void HeapPop(HP* php);
//返回堆顶数值函数
HPDataType HeapTop(HP* php);
//堆大小
size_t HeapSize(HP* php);
//判断堆是否为空
bool HeapEmpty(HP* php);

1、初始化函数

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

2、销毁函数

void DestroyHeap(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}

3、建堆

void PushHeap(HP* php,HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (realloc == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->capacity = newcapacity;
		php->a = tmp;
	}
	php->a[php->size] = x;

	php->size++;
	AdjustUp(php->a, php->size - 1);
}

  建堆的时候,我们将一个数组中的数一一入堆,那么就需要一个一个的申请空间,整体架构与顺序表相同,但是这里多了一个AdjustUp的函数,是因为我们堆只有大堆和小堆,源头数组里面的数不一定符合大堆或小堆的性质,所以我们需要对其进行调整。AdjustUp函数就是一个调整函数,通过名字我们也能知道,是向上调整。

  数据结构——堆(Heap)功能的实现,数据结构,算法,c语言

例如:我们创建一个小堆,最后末尾插入10时,10作为孩子结点,我们将其与它的父结点作比较,如果10小于它的父结点,我们将他们两个交换位置即可,然后再将10与它新的父结点比较大小,依次比较进行,直到10大于父结点,停止交换。

向上调整函数:

void AdjustUp(HPDataType* a, int child)
{
	assert(a);
//由孩子的位置求出父结点
	int parent = (child - 1) / 2;
	while (child>0)//因为是向上调整,所以孩子在向上调整的过程中会逐渐往源头数组下标为0的地方靠近
	{
		if (a[child] < a[parent])//父亲与孩子作比较
		{
			Swap_HP(&a[child],&a[parent]);//交换函数
			child = parent;//交换后,孩子替代父亲位置
			parent = (parent - 1) / 2;//寻找新父结点的位置
		}
		else
		{
			break;//如果孩子大于父亲则跳出循环
		}
	}
}

交换函数:

void Swap_HP(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

4、删除函数

  删除函数,我们单纯删除堆最后一个叶子结点其实用处不大,在这里,我们来实现如何删除根结点。我们直接删除根节点,剩下的组成新堆的话,那他们可能就已经乱了,就不会是堆了。

  所以我们用一种比较有新意的方法来实现:

  删除堆是删除堆顶的数据,将堆顶的数据根最后一个数据一换,然后删除数组最后一个数据,再进行向下调整算法。我们还是拿小堆为例。

数据结构——堆(Heap)功能的实现,数据结构,算法,c语言

  这里的向下调整算法与向上调整算法大致相同,向下调整算法是从上到下,如果父亲比较大的孩子大,则将父亲与较大的孩子交换位置,之后再与新的左右孩子中较大的一个进行比较,这样依次比较,直到它比孩子小为止。

void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;//假设左孩子大
	while (child < size)
	{
		if (child+1<size && a[child + 1] < a[child])//假设法 我们上们先假设左孩子大,这里再作比 
                                                    //较,如果右孩子大,那么child++就好了
		{
			child++;
		}
		if (a[child] < a[parent])//比较
		{
			Swap_HP(&a[child], &a[parent]);//交换位置
			parent = child;
			child = 2 * child + 1;
		}
		else
		{
			break;
		}
	}
	
}

5、返回堆顶元素

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

6、堆大小

size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

7、判断堆是否为空

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;	
}

三、堆功能的运用

#include"Heap.h"
int main()
{
	HP php;
	InitHeap(&php);//初始化
	int a[] = { 4,7,2,3,9,5,1 };
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		PushHeap(&php, a[i]);//建堆
	}
	
	while (!HeapEmpty(&php))
	{
		printf("%d ", HeapTop(&php));//打印堆顶元素
		HeapPop(&php);//删除堆顶元素,并找出第二小堆顶元素
	}
    DestroyHeap(HP*php);
	return 0;
}

打印堆顶元素后,HeapPop函数,每次删除完堆顶的元素之后,向下调整可以帮我们找到第二小的元素作为堆顶元素,所以我们根据这样来排序。

数据结构——堆(Heap)功能的实现,数据结构,算法,c语言文章来源地址https://www.toymoban.com/news/detail-808471.html

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

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

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

相关文章

  • 数据结构与算法——排序(C语言实现)

    ✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ 🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿 🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟 🌟🌟 追风赶月莫停留 🌟🌟 🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀 🌟🌟 平芜尽处是春山

    2024年04月09日
    浏览(55)
  • 数据结构和算法——用C语言实现所有图状结构及相关算法

    本文所有代码均在仓库中,这是一个完整的由纯C语言实现的可以存储任意类型元素的数据结构的工程项目。 首先是极好的工程意识,该项目是一个中大型的CMake项目,结构目录清晰,通过这个项目可以遇见许多工程问题并且可以培养自己的工程意识。 其次是优秀的封装性(

    2024年02月06日
    浏览(178)
  • 探索顺序表:数据结构中的秩序之美(c语言实现常见功能接口)

    在我们的数据结构探索中,我们已经探讨时间复杂度、空间复杂度。大家可以移步到我的上篇文章: 打开数据结构大门:深入理解时间与空间复杂度 今天,我们将深入研究另一个重要的主题——顺序表 全部的源代码大家可以去我github主页进行浏览:Nerosts/just-a-try: 学习c语言

    2024年02月03日
    浏览(53)
  • C语言数据结构-----顺序表(多功能动态顺序表的代码实现)

    本篇讲述了顺序表的相关知识,以及动态顺序表的代码实现。 顺序表和链表一般情况下都会叫他们线性表。 线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使 用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性

    2024年02月07日
    浏览(45)
  • 【算法与数据结构】 C语言实现单链表队列详解

    前面我们学习了队列的顺序表的实现,本节将用单链表实现队列。 队列也可以数组和链表的结构实现, 使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低 。下面我们先复习一下队列的基本概念: 队列:只允许在一端进行插入

    2024年04月11日
    浏览(55)
  • 头歌(C语言)-数据结构与算法-查找-第1关:实现折半查找

    任务描述 相关知识 编程要求 测试说明 任务描述 本关要求通过补全函数 BSL_FindKey 来实现在已排序的顺序表中查找关键码值为 key 的结点并返回该结点的编号。 相关知识 折半查找通常是针对顺序存储的线性表,线性表的结点按关键码从小到大排序,后面称之为折半查找的顺序

    2024年02月10日
    浏览(60)
  • 【C# 数据结构】Heap 堆

    作为 数据结构系类文章 的开篇文章,我们先了解一下C# 有哪些常用的数据结构 C# 是一种通用、面向对象的编程语言,它提供了许多常用的数据结构,以便在开发过程中高效地存储和操作数据。以下是一些在 C# 中常用的数据结构: 数组 (Array): 数组是一个固定大小的、相同类

    2024年02月15日
    浏览(33)
  • 数据结构与算法之美学习笔记:42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?

    本节课程思维导图: 利用 Trie 树,可以实现搜索引擎的提示功能,这样可以节省用户输入搜索的时间。实际上,搜索引擎在用户体验方面的优化还有很多,比如你可能经常会用的拼写纠错功能。 当你在搜索框中,一不小心输错单词时,搜索引擎会非常智能地检

    2024年02月03日
    浏览(57)
  • 头歌(C语言)-数据结构与算法-栈的实现-第1关:实现一个顺序存储的栈

    任务描述 相关知识 栈的基本概念 栈结构的定义(C) 顺序栈的操作 编程要求 测试说明 任务描述 本关任务是实现 step1/SeqStack.cpp 中的 SS_IsFull 、 SS_IsEmpty 、 SS_Length 、 SS_Push 和 SS_Pop 五个操作函数,以实现判断栈是否为满、是否为空、求栈元素个数、进栈和出栈等功能。 相关

    2024年02月07日
    浏览(60)
  • 头歌(C语言)-数据结构与算法-队列-第1关:实现一个顺序存储的队列

    任务描述 相关知识 顺序存储的队列 顺序队列的主要操作 编程要求 测试说明 任务描述 本关任务:实现 step1/SeqQueue.cpp 中的 SQ_IsEmpty 、 SQ_IsFull 、 SQ_Length 、 SQ_In 和 SQ_Out 五个操作函数,以实现判断队列是否为空、是否为满、求队列长度、队列元素入队和出队等功能。 相关知

    2024年02月06日
    浏览(142)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包