数据结构——lesson7二叉树 堆的介绍与实现

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

前言💞💞

啦啦啦~这里是土土数据结构学习笔记🥳🥳

数据结构——lesson7二叉树 堆的介绍与实现,数据结构,数据结构,c语言,算法,排序算法
💥个人主页:大耳朵土土垚的博客
💥 所属专栏:数据结构学习笔记
💥对于数据结构顺序表链表有疑问的都可以在上面数据结构的专栏进行学习哦~ 欢迎大家🥳🥳点赞✨收藏💖评论哦~🌹🌹🌹 有问题可以写在评论区或者私信我哦~

一、 堆的概念及结构

如果有一个关键码的集合K = { k1,k2 ,k3 ,…,kn-1 },把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足:ki <=k(2i+1 )且 ki<=k(2i+2) ( ki >=k(2i+1 )且 ki>=k(2i+2) ) i = 0,1,2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆的性质

  1. 堆中某个节点的值总是不大于或不小于其父节点的值;
  2. 堆总是一棵完全二叉树。
    数据结构——lesson7二叉树 堆的介绍与实现,数据结构,数据结构,c语言,算法,排序算法

✨✨简单来说大堆指的是父节点都大于子节点的完全二叉树;
小堆指的是父节点都小于子节点的完全二叉树;
大堆的根节点是最大的,小堆是最小的。

二、堆的实现

1.堆的创建

我们给出一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,现在我们通过算法,把它构建成一个堆。根节点左右子树不是堆,我们怎么调整呢?这里我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆。

下面是堆创建以及实现堆所需的函数,后文将一一介绍

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int HPDataType;
//构建一个结构体封装堆
typedef struct Heap
{
	HPDataType* a;//数组顺序表
	int size;//堆元素个数
	int capacity;//数组空间
}Heap;
//以下是实现堆的函数
// 堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
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);

2.堆的初始化

void HeapInit(Heap* hp)

//堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}

3.堆的删除(删除堆顶元素)

void HeapPop(Heap* hp)

在介绍堆的删除之前我们先介绍堆向下调整算法;
显而易见堆的删除不可能像顺序表那样删除尾部元素size–就行,我们需要玩点高深的,删除顶部元素,但删除顶部元素就没办法保证它删除后还是一个堆了,这就要利用我们下面介绍的向下调整算法。

int a[] = {1,8,3,5,7,6}; 

该数组逻辑结构可以看成一个完全二叉树如下图所示:
数据结构——lesson7二叉树 堆的介绍与实现,数据结构,数据结构,c语言,算法,排序算法

我们可以从图中看出它是一颗完全二叉树,但并不是所有的父节点都大于或小于其子节点,所以不是一个堆,接下来我们就可以通过下面介绍的堆向下调整算法将它调整为一个堆。

堆向下调整算法
现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。
向下调整算法有一个前提:左右子树必须是一个堆,才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

数据结构——lesson7二叉树 堆的介绍与实现,数据结构,数据结构,c语言,算法,排序算法

🥳🥳 ①下面介绍第一种向下调整为小堆
前提条件——左右子树都是小堆

//堆向下调整算法(小堆)
void AdjustDown(HPDataType* a, int n,int parent)
{
	
	int child = parent * 2 + 1;
	
	//向下调整
	while (parent < n)
	{
	//找到较小的孩子节点
		if (child + 1 < n && a[child] > a[child + 1])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
			break;
		
	}
}

因为要调整为小堆,所以要找到孩子中较小的一个进行比较;
如果父节点小于较小的孩子节点则直接break不需要调整,因为向下调整的前提条件是——左右子树都是小堆
调整前:
数据结构——lesson7二叉树 堆的介绍与实现,数据结构,数据结构,c语言,算法,排序算法
调整后:数据结构——lesson7二叉树 堆的介绍与实现,数据结构,数据结构,c语言,算法,排序算法

💞💞Swap函数在这里

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

🥳🥳②第二种向下调整为大堆;前提条件——左右子树都是大堆

//堆向下调整算法(大堆)
void AdjustDown(HPDataType* a, int n,int parent)
{
	
	int child = parent * 2 + 1;
	
	//向下调整
	while (child < n)
	{
	//找到较大的孩子节点
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
			break;
		
	}
}

因为要调整为大堆,所以要找到孩子中较大的一个进行比较; 如果父节点大于于较大的孩子节点则直接break不需要调整,因为向下调整的前提条件是——左右子树都是大堆

🎉🎉我们这里使用小堆向下调整,大家可以根据自己的需求选择哦~

学习完堆向下调整我们知道只要左右子树是一个堆,那么我们就可以从根节点开始向下调整直到整个二叉树成为一个堆;💫💫
所以删除堆顶元素我们就可以将堆顶元素与最后一个元素交换一下位置,这样除了根节点,其余父子关系都没变,左右子树还是堆,删除交换后的最后一个元素(也就是原来的根节点);🎉🎉
我们再利用堆向下调整算法,将整个二叉树再次复原为堆。🥳🥳

堆顶元素删除

// 堆的删除,删除堆顶元素
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));//判空函数将在后文介绍
	
	//交换首尾元素
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	
	//size要记得--,表示删除元素
	hp->size--;
	
	//向下调整算法
	AdjustDown(hp->a, hp->size, 0);

}

4.堆的插入

void HeapPush(Heap* hp, HPDataType x)

我们知道堆的父节点必须都大于或小于子节点,那么往一个堆中插入元素是没办法保证大于或小于其父节点的,所以我们插入之后需要调整这个二叉树来保证堆;
这里就要用到堆向上调整算法了;注意下面是小堆的调整

堆向上调整算法

//向上调整
void AdjustUp(HPDataType* a,int child)
{
	//找到双亲节点
	int parent = (child - 1) / 2;
	//向上调整
	while (child > 0)
	{
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
		
	}
}

堆向上调整类似于向下调整也有大堆小堆之分,大家可以依照堆的向下调整自己试试看写一下大堆的向上调整

堆的插入

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	//判断容量
	if (hp->size == hp->capacity)//容量满了扩容
	{
		int newcapacity = hp->capacity == 0 ? 0 : 2 * hp->capacity;
		HPDataType* new = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (new == NULL)
		{
			perror("realloc fail");
			return;
		}
		hp->a = new;
		hp->capacity = newcapacity;
	}
	//尾插
	hp->a[hp->size] = x;
	hp->size++;
	//向上调整算法
	AdjustUp(hp->a,hp->size-1);
}

这里要注意插入数据要判断容量,如果满了要用realloc函数扩容,对于realloc函数有疑问的可以看土土的动态内存函数博客🎉🎉——c语言动态内存函数介绍;
如果第一次扩容,就将空间扩为4个HPDataType,其余扩原来的两倍

5. 取堆顶的数据

HPDataType HeapTop(Heap* hp);

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));//判空
	return hp->a[0];//顶即下标为0的元素
}

6. 堆的数据个数

int HeapSize(Heap* hp)

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

堆的数据个数即为结构体中的size,直接返回即可

7.堆的销毁

void HeapDestory(Heap* hp)

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

,在内存中用realloc函数开辟空间用 free释放即可

💖💖判空函数在这里~
int HeapEmpty(Heap* hp)

// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

8.堆实现代码如下

#include"Heap.h"
//堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}
//交换函数
void Swap(HPDataType* a,HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

//堆向下调整算法
void AdjustDown(HPDataType* a, int n,int parent)
{
	//找到较小的孩子节点
	int child = parent * 2 + 1;
	
	//向下调整
	while (child < n)
	{
		if (child + 1 < n && a[child] > a[child + 1])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
			break;
		
	}
}

//向上调整
void AdjustUp(HPDataType* a,int child)
{
	//找到双亲节点
	int parent = (child - 1) / 2;
	//向上调整
	while (child > 0)
	{
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
		
	}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	//判断容量
	if (hp->size == hp->capacity)//容量满了扩容
	{
		int newcapacity = hp->capacity == 0 ? 0 : 2 * hp->capacity;
		HPDataType* new = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (new == NULL)
		{
			perror("realloc fail");
			return;
		}
		hp->a = new;
		hp->capacity = newcapacity;
	}
	//尾插
	hp->a[hp->size] = x;
	hp->size++;
	//向上调整算法
	AdjustUp(hp->a,hp->size-1);
}
// 堆的删除,删除堆顶元素
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	//向下调整算法
	AdjustDown(hp->a, hp->size, 0);

}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;

}
// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

测试代码如下:

#include"Heap.h"
int main()
{
	Heap hp;
	HeapInit(&hp);
	int a[] = { 65,100,70,32,50,60 };
	for (int i = 0; i < 6; i++)
	{
		HeapPush(&hp, a[i]);
	}
	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
		printf("%d\n", top);
		HeapPop(&hp);
	}

	return 0;
	
}

运行结果如下:
数据结构——lesson7二叉树 堆的介绍与实现,数据结构,数据结构,c语言,算法,排序算法

居然是升序诶~大家知道原因吗✨✨ 可以根据上面的代码和介绍理解为自己解答哦~土土将在下一篇博客介绍堆的应用,会详细介绍堆排序哦 ~💖💖

三、结语

以上就是堆的介绍和实现啦~✨✨需要注意的是堆有大堆小堆之分,相应的函数也就有两种,这里简单介绍了小堆的实现,大堆介绍了一点,大家可以通过上面介绍的自己探索大堆的实现,此外堆向上调整与向下调整是一个重难点大家要多花时间去理解与记忆哦 ~完结撒花 ~💖🎉🎉🥳文章来源地址https://www.toymoban.com/news/detail-838459.html

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

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

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

相关文章

  • 【数据结构和算法】---二叉树(2)--堆的实现和应用

    如果有一个数字集合,并把它的所有元素 按完全二叉树的顺序存储方式存储在一个一维数组中 ,且在逻辑结构(即二叉树)中,如果 每个父亲节点都大于它的孩子节点那么此堆可以称为大堆 ;那么如果 每个父亲节点都小于它的孩子节点那么此堆可以称为小堆 。 堆的 性质

    2024年02月03日
    浏览(47)
  • 速学数据结构 | 二叉树堆的实现详解篇

    🎬 鸽芷咕 :个人主页  🔥 个人专栏 :《速学数据结构》 《C语言进阶篇》 ⛺️生活的理想,就是为了理想的生活!    🌈 hello! 各位宝子们大家好啊,二叉树的概念大家都了解了那么我们今天就看一下    ⛳️ 顺序存储究竟是怎么存储的,如何实现增删查改这些功能。

    2024年02月01日
    浏览(41)
  • 【数据结构】树二叉树的概念以及堆的详解

    ✨链接1:【数据结构】顺序表 ✨链接2:【数据结构】单链表 ✨链接3:【数据结构】双向带头循环链表 ✨链接4:【数据结构】栈和队列 百度百科的解释 :树是一种 非线性 的数据结构,它是由n(n≥0)个有限节点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像

    2024年02月16日
    浏览(40)
  • 【数据结构】堆的应用+TOP-K问题+二叉树遍历

    欢迎来到我的: 世界 希望作者的文章对你有所帮助,有不足的地方还请指正,大家一起学习交流 ! 该篇文章写到主要是:堆排序、 TOP-K问题、二叉树链式结构的实现、二叉树的遍历等等;如果有朋友还不太了解堆以及二叉树可以翻看我的上一篇博客:堆和二叉树的概念; 最

    2024年02月07日
    浏览(54)
  • 【数据结构】由完全二叉树引申出的堆的实现

    关于“堆”,百度百科上是这么说的: ——————————引自百度百科 由上面可知,我们可以将堆理解成一个数组,也可以理解成一个完全二叉树。 其实由于完全二叉树的特殊性,其本身就可以使用一个数组来存储。 在之前的二叉树的实现中,我们已经知道完全二叉树

    2024年02月08日
    浏览(43)
  • 【数据结构—二叉树的基础知识介绍和堆的实现(顺序表)】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 1.树概念及结构 1.1树的概念 1.2 树的相关概念  1.3 树的表示 1.4 树在实际中的运用(表示文件系统的目录树结构) 2.二叉树概念及结构 2.1概念 2.2 特殊的二叉树: 2.3 二叉树的存储结构

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

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

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

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

    2024年02月08日
    浏览(45)
  • 【数据结构】--- 博主拍了拍你并向你扔了一“堆”二叉树(堆的概念+结构+代码实现)

    👧个人主页:@小沈熬夜秃头中୧⍤⃝❅ 😚小编介绍:欢迎来到我的乱七八糟小星球🌝 📋专栏:数据结构 🔑本章内容:二叉树—堆 送给各位💌:心有所期全力以赴定有所成. 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示:以下是本篇文章正文内容,下面案例可供参考

    2024年02月06日
    浏览(38)
  • 数据结构学习记录——什么是堆(优先队列、堆的概念、最大堆最小堆、优先队列的完全二叉树表示、堆的特性、堆的抽象数据类型描述)

    目录 优先队列 若采用数组或链表实现优先队列  数组 链表 有序数组 有序链表 总结 若采用二叉搜索树来实现优先队列 最大堆 堆的概念 优先队列的完全二叉树表示 堆的两个特性  结构性 有序性 【例】最大堆和最小堆 【例】不是堆 堆的抽象数据类型描述 优先队列 (Prio

    2024年02月02日
    浏览(52)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包