【数据结构】二叉树-堆(函数实现)

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

 🌈个人主页:秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343
🔥 系列专栏:《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482

【数据结构】二叉树-堆(函数实现),数据结构,数据结构,c语言,二叉树,堆​​

 

目录

头文件

函数实现

初始化

销毁

插入

向上调整

交换两个元素

向下调整

删除(默认删堆顶元素)

找堆顶元素

堆的大小

是否为空


   前言

    💬 hello! 各位铁子们大家好哇。

             今日更新了堆的基本函数实现
    🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

头文件

#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(HPDataType* a, int size, int parent);

函数实现

初始化

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

销毁

void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

插入

//O(log N)
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, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity; 
	}

	php->a[php->size] = x;
	php->size++;

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

向上调整

//小堆
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

交换两个元素

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

向下调整

//小堆
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++;
		}
		if (a[child] < a[parent])
		{
			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[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a,php->size,0);
}

找堆顶元素

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size>0);

	return php->a[0];
}

堆的大小

size_t HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

是否为空

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

注意:上面所建的堆是小堆,若需要建大堆,只需修改向上和向下调整的函数。文章来源地址https://www.toymoban.com/news/detail-814778.html

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

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

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

相关文章

  • 数据结构入门(C语言版)二叉树链式结构的实现

    简单回顾一下二叉树的 概念: ★ 空树 ★非空:根节点,根节点的左子树、根节点的右子树组成的。 从概念中可以看出,二叉树定义是递归式的,因此后序基本操作中基本都是按照该概念实现的。 下面我们先看二叉树的结构体定义以及创建 首先结构体的定义是元素本身,以

    2023年04月23日
    浏览(47)
  • 数据结构(C语言实现)——二叉树的概念及二叉树顺序结构和链式结构的实现(堆排序+TOP-K问题+链式二叉树相关操作)

    前面学习了数据结构中线性结构的几种结构,顺序表,链表,栈和队列等,今天我们来学习一种非线性的数据结构——树。由于二叉树是数据结构中的一个重点和难点,所以本文着重介绍二叉树的相关概念和性质,以及二叉树的应用。 树是一种非线性的数据结构,它是由n(

    2023年04月21日
    浏览(45)
  • C语言数据结构初阶(10)----二叉树的实现

    · CSDN的uu们,大家好。这里是C语言数据结构的第十讲。 · 目标:前路坎坷,披荆斩棘,扶摇直上。 · 博客主页: @姬如祎 · 收录专栏: 数据结构与算法     目录 1. 函数接口一览 2. 函数接口的实现 2.1 BTNode* BuyNode(BTDataType x) 的实现 2.2 BTNode* CreateTree() 的实现  2.3 void

    2023年04月08日
    浏览(44)
  • 二叉树的基本操作-C语言实现-数据结构作业

    目录  (1)二叉树的创建; (2)二叉树的先序、中序和后序遍历输出; (3)输出二叉树的叶子节点和度为2的节点的数量; (4)输出二叉树的深度; (5)将二叉树所有节点的左右子树互换(左子树变右子树,右子树变左子树); (6)参考书上,二叉树按层次输出(一行输出一层); (7)删除二

    2024年02月04日
    浏览(48)
  • 数据结构初阶之基础二叉树(C语言实现)

    📃 博客主页: 小镇敲码人 💞 热门专栏:数据结构与算法 🚀 欢迎关注:👍点赞 👂🏽留言 😍收藏 🌏 任尔江湖满血骨,我自踏雪寻梅香。 万千浮云遮碧月,独傲天下百坚强。 男儿应有龙腾志,盖世一意转洪荒。 莫使此生无痕度,终归人间一捧黄。🍎🍎🍎 ❤️ 什么

    2024年03月19日
    浏览(43)
  • 【数据结构】线索二叉树(适用场景+图文推导过程+C语言代码实现)

    普通二叉树(如下图): 空间浪费 :存在大量“∧”,该空间未利用。 时间效率 :查找一次结点的前驱、后继就需要遍历一次,时间效率低。         在实际问题中,如果所用的 二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继,那么采用线索二叉链表

    2024年02月04日
    浏览(36)
  • 数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用

    普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用 顺序结构的数组来存储 ,需要注意的是 这里的堆和操作系统虚拟进程地址空间中的堆是两回事 ,一个是 数据结构 ,一

    2023年04月19日
    浏览(53)
  • 【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】六、线性表中的队列(链式结构实现队列)-CSDN博客  ===========================

    2024年02月08日
    浏览(45)
  • [C语言实现]数据结构堆之《害怕二叉树所以天赋全点到堆上了》

    🥰作者: FlashRider 🌏专栏: 数据结构 🍖知识概要:详解 堆 的概念、小根堆与大根堆的区别、以及代码实现。 目录 什么是堆? 如何实现堆? 代码实现堆(小根堆) 定义堆以及堆的初始化和销毁。 堆的插入 堆的删除 获取堆的元素长度和获取堆顶元素 代码测试 TopK问题 我们先

    2024年02月09日
    浏览(35)
  • 数据结构---二叉树(C语言)

    空树 非空:根节点,根节点的左子树、根节点的右子树组成的。 从二叉树的定义来看,二叉树是递归定义的,因此我们可以用递归的形式来遍历二叉树。 1.1.1二叉树前中后序遍历(递归版) 访问根结点的顺序不同。 1.1.2 层序遍历 层序遍历是按照二叉树的高度,一层一层遍

    2024年02月06日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包