[数据结构 -- C语言] 堆(Heap),你小子就是堆,看我如何透彻的将你拿捏

这篇具有很好参考价值的文章主要介绍了[数据结构 -- C语言] 堆(Heap),你小子就是堆,看我如何透彻的将你拿捏。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1、堆的概念及结构

1.1 概念(概念总是重要的)

1.2 结构,分为两种

1.2.1 小堆/小根堆示例

1.2.2 大堆/大根堆示例

2、堆的接口

3、接口实现

3.1 堆的初始化

3.2 堆的销毁

3.3 堆的插入

功能分析:

功能实现:

3.4 堆的删除

功能分析:

功能实现:

3.5 取堆顶的数据

3.6 堆的数据个数

3.7 堆的判空

4、完整代码


1、堆的概念及结构

1.1 概念(概念总是重要的)

[数据结构 -- C语言] 堆(Heap),你小子就是堆,看我如何透彻的将你拿捏

上面这一段是堆的概念,但是这也太没劲了吧,我们来通俗的讲一下,敲黑板了嗷:

堆的本质是一个完全二叉树。

大堆(也叫大根堆):父节点大于/等于子节点。

小对(也叫小根堆):父节点小于/等于子节点。

如果不满足上面的条件,那么就不是堆。

堆的性质:

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

1.2 结构,分为两种

1.2.1 小堆/小根堆示例

[数据结构 -- C语言] 堆(Heap),你小子就是堆,看我如何透彻的将你拿捏

1.2.2 大堆/大根堆示例

[数据结构 -- C语言] 堆(Heap),你小子就是堆,看我如何透彻的将你拿捏

我们来看一个题目:

下列关键字序列为堆的是:(A)

A 100,60,70,50,32,65

B 60,70,65,50,32,100

C 65,100,70,32,50,60

D 70,65,100,32,50,60

E 32,50,100,70,65,60

F 50,100,70,65,60,32

分析:我们画图来分析

[数据结构 -- C语言] 堆(Heap),你小子就是堆,看我如何透彻的将你拿捏

2、堆的接口

本篇文章是以小堆为例来实现的。堆的数据存储是用数组存的,数据的内存中的存储结构是顺序存储的,我们为了好理解,以逻辑结构理解的。

堆的接口有:初始化、销毁、插入、删除、取堆顶、堆的数据个数、判空。

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

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;

// 堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
//交换
void Swap(HPDataType* p1, HPDataType* p2);
//向上调整
void AdjustUp(HPDataType* a, int child);
//向下调整
void AdjustDown(HPDataType* a, int size, int parent);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);

3、接口实现

我们这些接口好多都是与之前的数据结构文章是类似的,前面已经多次讲解,这里就不再讲解了,要是有看不懂的地方可以参考之前的数据结构文章。

3.1 堆的初始化

void HeapInit(Heap* hp)
{
	assert(hp);

	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}

3.2 堆的销毁

void HeapDestory(Heap* hp)
{
	assert(hp);

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

3.3 堆的插入

堆的插入是比较复杂的,也是一个难点,我们先来分析,再去实现功能。

功能分析:

1、插入的时候我们先要看数组是否需要扩容,先判满,如果空间满了就先扩容,然后将新元素插入到数组的尾部;

2、我们新插入一个元素,就需要去分析一下此堆是否满足小堆的结构,如果不满足我们就需要将新元素向上调整。

3、向上调整过程分析:

我们来举例分析一下:如果给一个小堆插入一个元素后,堆的结构被破坏,如何调整才能恢复小堆的结构。

[数据结构 -- C语言] 堆(Heap),你小子就是堆,看我如何透彻的将你拿捏

a、当我们发现给小堆插入一个 10 后,10 比父节点 28 小,破坏了小堆的结构,我们需要对堆进行调整;

b、堆的物理结构是数组,所以我们可以通过下标来找到父节点,这里找父节点的公式:parent = (child-1)/2。当我们找到父节点后,让子节点与父节点去比较,如果小于父节点我们就让两个节点的元素交换,交换后的父节点与它的父节点可能也不满足小堆,因此需要不断的向上调整;

c、循环去比较调整,当child = 0 时,我们的调整就结束了,因此我们的循环判断条件为 child > 0。

注意:当有一次调整完后,我们的堆已经成为了小堆,就跳出循环。

我们根据上面的思路来画图走一遍:

[数据结构 -- C语言] 堆(Heap),你小子就是堆,看我如何透彻的将你拿捏

我们对功能的分析就结束了,开始实现功能。

功能实现:

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

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 = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//log N 
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);

	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (NULL == tmp)
		{
			perror("realloc fail:");
		}

		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;

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

交换与向上调整后面我们会复用的,因此我们将其两个功能封装成函数。

3.4 堆的删除

堆的删除是删堆顶的元素。

思路:堆顶数据与最后一个数据交换,删掉最后一个数据,再从堆顶向下调整。

功能分析:

我们这里删除堆顶数据的时候不能直接删,直接删除堆顶数据就会破坏堆结构,再去建堆时间复杂度太高,不推荐,这里我们介绍一种方法,复杂度较低:

1、我们将堆顶数据与最后一个数据先交换,再删除最后一个数据,最后从堆顶向下调整;

2、向下调整比较复杂,我们下面进行分析并画图来讲解:

a、此时我们的 parent节点 是堆顶节点,接下来我们需要找到 2 个子节点中小的哪个作为孩子节点,这里的找子节点公式:child = parent*2 + 1;

b、如果孩子小于父亲,就交换,并且继续往下调整,让parent 走到 child 位置,再去算 child 位置;

c、当孩子下标大于数组的大小时,循环就结束,整个调整就完成了。

注意:当有一次调整完后,我们的堆已经成为了小堆,就跳出循环。

功能实现:

void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)//当child大于了数组大小就跳出循环
	{
		//找出左右孩子中小/大的那个(假设法)
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[parent], &a[child]);

			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//log N
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);
}

3.5 取堆顶的数据

HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	return hp->a[0];
}

3.6 堆的数据个数

int HeapSize(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	return hp->size;
}

3.7 堆的判空

bool HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->size == 0;
}

4、完整代码

完整代码在代码仓库:Heap · 小白在努力jy/DataStructure - 码云 - 开源中国 (gitee.com)文章来源地址https://www.toymoban.com/news/detail-468123.html

到了这里,关于[数据结构 -- C语言] 堆(Heap),你小子就是堆,看我如何透彻的将你拿捏的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构】堆(Heap):堆的实现、堆排序、TOP-K问题

    目录 堆的概念及结构 ​编辑 堆的实现  实现堆的接口 堆的初始化 堆的打印 堆的销毁 获取最顶的根数据  交换 堆的插入(插入最后) 向上调整(这次用的是小堆) 堆的删除(删除根) 向下调整(这次用的小堆) 堆排序 TOP-K问题 如果有一个关键码的集合 K = { , , , …

    2024年02月05日
    浏览(51)
  • 【科大讯飞星火】如果说数据结构统治着整个计算机程序的世界,那么算法就可以被看作是程序员的全部装备。一般的来看的话,计算机本质就是信息的存储和处理的技术

    计算机科学是研究计算机及其相关技术的学科。它涵盖了多个领域,包括算法、数据结构、编程语言、操作系统、计算机网络等。本章将介绍计算机科学的基本概念和原理。 计算机硬件是指计算机的物理部分,包括中央处理器(CPU)、内存、硬盘、显示器、键盘等。其中,CPU

    2024年02月08日
    浏览(63)
  • 【数据结构】C语言结构体详解

    目录 前言 一、结构体的定义 二、定义结构体变量 三、结构体变量的初始化 四、使用typedef声明新数据类型名 五、指向结构体变量的指针 总结 🌈嗨!我是Filotimo__🌈。很高兴与大家相识,希望我的博客能对你有所帮助。 💡本文由Filotimo__✍️原创,首发于CSDN📚。 📣如需转

    2024年02月04日
    浏览(46)
  • 『初阶数据结构 • C语言』① - 数据结构为何重要

    本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余,我决定把这本书精彩的部分摘录出来与大家分享。 数组是计算机科学中最基本的数据结构之一。如果你用过数组,那么应该知道它就是一个含有 数据的列表。它有多种用途,适用于各种场景,下面

    2024年02月16日
    浏览(45)
  • R语言数据结构(三)数据框

    数据结构是指在计算机中存储和组织数据的方式,不同的数据结构有不同的特点和适用场景。R语言中的常用数据结构,包括向量、矩阵、数组、列表和数据框。关于数据结构的使用,我们将分四篇文章分别介绍每种数据结构的操作方法和代码示例。 为方便大家理解记忆,对

    2024年01月15日
    浏览(38)
  • 【C语言】【数据结构】自定义类型:结构体

    这是一篇对结构体的详细介绍,这篇文章对结构体声明、结构体的自引用、结构体的初始化、结构体的内存分布和对齐规则、库函数offsetof、以及进行内存对齐的原因、如何修改默认对齐数、结构体传参进行介绍和说明。                  ✨  猪巴戒 :个人主页✨      

    2024年02月05日
    浏览(32)
  • 数据结构初阶(用C语言实现简单数据结构)--栈和队列

    ✨✨欢迎来到T_X_Parallel的博客!!       🛰️博客主页:T_X_Parallel       🛰️专栏 : 数据结构初阶       🛰️欢迎关注:👍点赞🙌收藏✍️留言 这小猫真好看 言归正传,通过上篇有关顺序表和链表的博客,可以了解到线性表的一些大致特征,这篇博

    2024年02月08日
    浏览(40)
  • 数据结构——二叉树基础结构篇(C语言)

    现在是北京时间2023年6月13日9点11分。从决定要开始减脂之后,饥饿总是伴随着我。一觉起来肚子咕咕叫,我还是想先把文章发了再吃第一餐。燕麦加蛋白粉几乎伴随了我大学的第一年早饭。昨天练了一个小时背,练背后还做了45分钟有氧。空腹训练没有影响我的训练状态。这

    2024年02月08日
    浏览(38)
  • C语言数据结构--链表

    顺序表的问题及思考 问题: 1. 中间/头部的插入删除,时间复杂度为O(N) 2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有

    2024年02月05日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包