【数据结构】这堆是什么

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

目录

1.二叉树的顺序结构

2.堆的概念及结构

3.堆的实现

3.1 向上调整算法与向下调整算法

3.2 堆的创建

 3.3 建堆的空间复杂度

3.4 堆的插入

 3.5 堆的删除

 3.6 堆的代码的实现

4.堆的应用

4.1 堆排序

4.2 TOP-K问题


首先,堆是一种数据结构,一种特殊的完全二叉树,采用顺序结构存储,在学习堆之前,我们先学习一下二叉树的顺序结构,再开始学习本篇文章的重点 ---

1.二叉树的顺序结构

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

完全二叉树的顺序存储:

【数据结构】这堆是什么,数据结构与算法,数据结构,c语言,顺序表,排序算法,堆排序

非完全二叉树的顺序存储:

【数据结构】这堆是什么,数据结构与算法,数据结构,c语言,顺序表,排序算法,堆排序 可以发现非完全二叉树可能会存在大量的空间浪费。

2.堆的概念及结构

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

概括来说:

堆有大根堆小根堆之分,简称大堆小堆:

大堆:堆内所有父节点都大于子节点。根节点最大。

小堆:堆内所有父节点都小于子节点。根节点最小。

堆的性质:

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

示例:

【数据结构】这堆是什么,数据结构与算法,数据结构,c语言,顺序表,排序算法,堆排序

例题:

1.下列关键字序列为堆的是:()
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

答案A

3.堆的实现

3.1 向上调整算法与向下调整算法

建堆有两种算法,一种是向上调整算法,一种是向下调整算法。现在我们给出一个数组,逻辑上看做一颗完全二叉树。

向上调整算法:

前提:前面元素已经构成堆,才能调整

比如在下面小堆后面插入5

【数据结构】这堆是什么,数据结构与算法,数据结构,c语言,顺序表,排序算法,堆排序

 会将插入的数据向上调整到合适的位置

代码实现:

//交换
void Swap(HeapDataType* p1, HeapDataType* p2)
{
	HeapDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//小堆
void AdjustUp(HeapDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] < arr[parent])
		{
            //交换
			Swap(&arr[child],&arr[parent]);
			
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

 建立大堆和小堆的向上调整算法判断条件不同,略有差异。

向下调整算法:

我们通过从根节点开始的向下调整算法,可以把它调整成一个小堆。

向下调整算法有一个前提:左右子树必须是一个堆,才能调整

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

以27为根的左右子树,都满足小堆的性质,只有根节点不满足,因此只需将根节点往下调整到合适的位置即可形成堆

【数据结构】这堆是什么,数据结构与算法,数据结构,c语言,顺序表,排序算法,堆排序

代码实现

//向下调整
//完全二叉树没有左孩子,肯定没有右孩子   n是数组元素个数
void AdjustDown(HeapDataType* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
        //找出左右孩子中最小的
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
            //交换
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

3.2 堆的创建

这里用向下调整算法创建,因为向上调整法时间复杂度较大,后面会讲

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

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

步骤如下: 

【数据结构】这堆是什么,数据结构与算法,数据结构,c语言,顺序表,排序算法,堆排序

 3.3 建堆的空间复杂度

因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个节点不影响最终结果):

向下调整算法建堆:

【数据结构】这堆是什么,数据结构与算法,数据结构,c语言,顺序表,排序算法,堆排序

 所以向下调整算法建堆的时间复杂度为O(N)。

向上调整算法建堆:

向上调整算法需要从第2个节点开始向上调整,调整好之后,第3个节点向上调整,依次向后,直到调完。

【数据结构】这堆是什么,数据结构与算法,数据结构,c语言,顺序表,排序算法,堆排序

 所以向上调整算法建堆的时间复杂度为O(N*(logN))。

所以这里推荐使用向下调整算法。

3.4 堆的插入

先插入一个10到数组的尾上,再进行向上调整算法,直到满足堆。
【数据结构】这堆是什么,数据结构与算法,数据结构,c语言,顺序表,排序算法,堆排序

 3.5 堆的删除

删除堆是删除堆顶的数据,将堆顶的数据根最后一个数据一换,然后删除数组最后一个数据,再进行向下调整算法
【数据结构】这堆是什么,数据结构与算法,数据结构,c语言,顺序表,排序算法,堆排序

 3.6 堆的代码的实现

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

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
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);

具体实现:

//交换元素
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType t = *p1;
	*p1 = *p2;
	*p2 = t;
}
//向下调整 小堆
void AdjustDown(HPDataType* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//找最小子树
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}

		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			return;
		}
	}
}
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (hp->a == NULL)
	{
		return;
	}
	hp->capacity = n;
	hp->size = n;
	for (int i = 0; i < n; i++)
	{
		hp->a[i] = a[i];
	}
	
	for (int i = (n-1-1)/2; i >= 0; i--)
	{
		AdjustDown(hp->a, n, i);
	}
 }
// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

//向上调整  小堆
void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);

			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			return;
		}
	}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->a == NULL ? 4 : hp->capacity * 2;
		HPDataType* ptr = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (ptr == NULL)
		{
			perror("realloc fail");
			return;
		}
		hp->a = ptr;
		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;
}

4.堆的应用

4.1 堆排序

堆排序即利用堆的思想来进行排序,总共分为两个步骤:
1.建堆

  • 升序:建大堆
  • 降序:建小堆

2.利用堆删除思想来进行排序。

建堆和堆删除中都用到了向下调整,因此掌握了向下调整,就可以完成堆排序

示例:升序:

#include<stdio.h>
//交换
void swap(int* p1, int* p2)
{
	int t = *p1;
	*p1 = *p2;
	*p2 = t;
}

//向下调整 大堆
void Adjustdown(int* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}
		if (arr[child] > arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	//建堆  升序建大堆
	//向下调整
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		Adjustdown(a, n, i);
	}
	
	//排序 
	int end = n - 1;
	while (end)
	{
		swap(&a[end], &a[0]);
		Adjustdown(a, end, 0);
		end--;
	}
}

int main()
{
	
	int arr[] = { 10,50,40,20,30,60,70 };
	int sz = sizeof(arr) / sizeof(int);
	HeapSort(arr, sz);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	
	return 0;
}

4.2 TOP-K问题

TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:

1.用数据集合中前K个元素来建堆

  • 前k个最大的元素,则建小堆
  • 前k个最小的元素,则建大堆

2.用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素,再向下调整。

将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

示例代码:这里需要生成文件后打开文件把几个数改成较大的值,模拟数据中的最大值,再注释掉CreateNDate()函数,模拟TOP-K问题,因为再写文件会把原来的数据覆盖掉。

#include<stdio.h>
#include<time.h>
void swap(int* p1, int* p2)
{
	int t = *p1;
	*p1 = *p2;
	*p2 = t;
}

//小堆
void Adjustdown(int* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void CreateNDate()
{
	// 造数据
	int n = 10000;
	srand((unsigned int)time(NULL));
	FILE* file = fopen("data.txt", "w");
	for (int i = 0; i < n; i++)
	{
		fprintf(file,"%d\n", rand() % 10000);//生成10000以内的随机数
	}

	fclose(file);
}

void PrintTopK(int k)//最大的k个数
{
	CreateNDate();//造数据,选这些数据中的最大值
	FILE* file = fopen("data.txt", "r");

	//建立小堆
	int* arr = (int*)malloc(sizeof(int) * k);
	for (int i = 0; i < k; i++)
	{
		fscanf(file, "%d", &arr[i]);
	}
	for (int i = (k-1-1)/2; i >=0 ; i--)
	{
		Adjustdown(arr, k, i);
	}

	int a = 0;
	while (fscanf(file, "%d", &a)!=EOF)
	{
		if (arr[0] < a)
		{
			swap(&arr[0], &a);
		}
		Adjustdown(arr, k, 0);
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", arr[i]);
	}
	fclose(file);
	free(arr);
}


int main()
{
	PrintTopK(5);
	return 0;
}

本篇结束
 文章来源地址https://www.toymoban.com/news/detail-618148.html

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

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

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

相关文章

  • 数据结构和算法——用C语言实现所有图状结构及相关算法

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

    2024年02月06日
    浏览(178)
  • 数据结构与算法——排序(C语言实现)

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

    2024年04月09日
    浏览(55)
  • C语言 数据结构--栈 括号匹配算法

    今天这一期使用栈来完成括号匹配算法 ① 栈结构 ② 初始化栈 ③ 入栈 ④ 出栈 ⑤ 判断栈是否为空 ⑤ 括号匹配 完整代码: 结果: (1)括号序列为char str[]={\\\'(\\\',\\\'{\\\',\\\'[\\\',\\\']\\\',\\\'}\\\',\\\')\\\'}; (2)括号序列为char str1[]={\\\'{\\\',\\\'(\\\',\\\'}\\\',\\\']\\\'};    

    2024年02月05日
    浏览(53)
  • C语言 数据结构与算法 I

    因为之前写算法都是用C++,也有了些C++基础,变量常量数据类型就跳过去吧。 首先是环境,学C++时候用Clion,C语言也用它写吧~ 新建项目,选C执行文件,语言标准。。。就先默认C99吧,反正是测试环境,应该问题不大 直接运行一手 嗯。。JB家的新UI。。真是。。。。。。。一

    2024年02月09日
    浏览(41)
  • 数据结构与算法这么难,为什么我们还要学习?

    提到数据结构与算法,就一定会伴随着诸多所谓的坚持和抱怨。同时,还有两个词总是出现,一个是内功,是对知识的定位,一个是吃透,是对自己

    2024年01月19日
    浏览(54)
  • 【C/C++数据结构与算法】C语言数据存储

    目录 一、大小端存储 二、整型提升和截断 三、数据的二进制存储 四、结构体内存对齐 大端存储 :数据的低位字节存储在高地址 小端存储 :数据的低位字节存储在低地址 不同编译器有不同的存储方式 提升 :短字节数据类型 --- 长字节数据类型 截断 :长字节数据类型 --

    2024年02月09日
    浏览(42)
  • 【学习笔记】数据结构算法文档(类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日
    浏览(42)
  • (C语言)数据结构算法-病毒感染检测(BF算法&&KMP算法)

    病毒感染检测: 医学研究者最近发现了某些新病毒,得知它们的DNA序列都是环状的。为了快速检测出患者是否感染了相应的病毒,研究者将患者的DNA和病毒的DNA均表示成一些字母组成的字符串序列,然后检测某种病毒DNA序列是否在患者的DNA序列中出现过,如果出现过,则此人

    2024年02月08日
    浏览(47)
  • [数据结构-C语言] 算法的时间复杂度

    目录 1.算法的复杂度 2.时间复杂度 2.1 时间复杂度的概念 2.2 大O的渐进表示法 3、常见时间复杂度计算举例 3.1 冒泡排序 3.2 二分查找 3.3 阶乘递归 3.4 斐波那契数列 1.算法的复杂度 算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此 衡量一个算法的

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

    本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余,我决定把这本书精彩的部分摘录出来与大家分享。   算法这个词听起来很深奥,其实不然。它只是解决某个问题的一套流程。  准备一碗麦片的流程也可以说是一种算法,它包含以下 4步(对我来说

    2024年02月14日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包