DS:二叉树的顺序结构及堆的实现

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

DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记

                                       创作不易,兄弟们给个三连!!

一、二叉树的顺序存储

DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记

      顺序结构指的是利用数组来存储,一般只适用于表示完全二叉树,原因如上图,存储不完全二叉树会造成空间上的浪费,有的人又会问,为什么图中空的位置不能存储呢??原因是我们需要根据数组的下标关系才能访问到对应的节点!!有以下两个下标关系公式:

1、父亲找孩子:leftchild=parent*2+1,rightchild=parent*2+2

2、孩子找父亲:parent=(child-1)/2   要注意,这边无论用左孩子算还是右孩子算都是可以的,因为一般俩说,(child-1)/2 由于int类型向下取整的特点,所以得到的结果都是一样的!!

      所以我们想要上面这种方式去访问节点,并且还不希望有大量的空间浪费,现实中只有堆才会使用数组存储,二叉树的顺序存储中在物理上是一个数组,再逻辑上是一颗二叉树!!

二、堆的概念及结构

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

   如果有一个关键码的集合k,我们将他的全部元素按照完全二叉树的存储逻辑放在一个一维数组中,则成为堆,根节点最大的堆叫做大堆,根节点最小的堆叫做小堆。 

堆的性质:

1、堆中某个节点的值总是不大于或不小于其父节点的值

2、堆总是一颗完全二叉树

DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记

注意:并不一定有序 

三、堆的实现

假设我们实现小堆

3.1 相关结构体的创建

跟顺序表的形式是一样的,但是换了个名字

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

3.2 堆的初始化

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

3.3 堆的插入

堆的插入很简单,但是我们要保证堆插入后还能维持堆的形状

DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记

所以我们在插入后,还要进行向上调整,也就是孩子要根据下标关系找到自己的父亲去比较,小就交换

void HeapPush(Heap* php, HPDataType x)
{
	assert(php);
	//首先要判断是否需要扩容
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* temp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);
		if (temp == NULL)
		{
			perror("malloc fail");
			exit(1);
		}
	    //扩容成功
		php->a = temp;
		php->capacity = newcapacity;
	}
     //扩容后,我们插入这个元素并size++
	php->a[php->size++] = x;
	//但是插入之后可能会破坏堆的结构,所以我们需要这个元素和他的父辈进行逐个比较, 
	AdjustUp(php->a,php->size-1);//封装一个向上调整函数,传入数组和新加元素的下标
}

3.4 向上调整算法

void AdjustUp(HPDataType* a, int child)
{
	assert(a);
    //通过孩子找父亲  parent=(child-1)/2
	int parent = (child - 1) / 2;
	//孩子和父亲开始比较,如果孩子小,就交换,如果孩子大,退出循环
	while (child>0)//如果孩子变成了根节点,就没有必要再找了,因为已经没有父母了
		//如果用parent>=0来判断,那么由于(0-1)/2是-1/2,取整后还是0,就会一直死循环,所以必须用孩子来当循环条件
	{
		if (a[child] < a[parent])//孩子小,交换
		{
			Swap(&a[child], &a[parent]);
			//但是交换过后,可能还需要继续往上比,所以我们要让原来的父亲变成孩子,然后再找新的父亲进行比较
			child = parent;
			parent = (child - 1) / 2;
		}
		else//孩子大,退出
			break;
	}
}

注:这里的向上调整算法和后面向下调整算法我们都不用跟堆有关的接口,原因就是这个算法的运用范围很广,可以用在堆排序以及top-k问题中!!

3.5 交换函数

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

3.6 堆的删除

         一般来说,如果直接删除堆的最后一个元素,其实是没什么意义的,一行代码就可以搞定,没必要封装什么函数,所以这里的堆的删除指的是删除根部的元素!!

        DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记

void HeapPop(Heap* php)//一般来说,堆中的删除指的是删除根位置的数据
//如果直接删除根然后往前挪动一位,那么亲缘关系就会十分混乱,为了能够尽量在调整中减少对关系的改变
//我们将根部元素与最后一个元素进行交换之后再删除,此时的根是原先的最后一个元素
//然后将该元素进行向下调整(封装一个函数,传入数组、元素个数、)
{
	assert(php);
	assert(!HeapEmpty(php));//为空的话没有删除的必要
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	//开始向下调整
	AdjustDown(php->a, php->size,0);
}

3.7 向下调整算法

void AdjustDown(HPDataType* a, int n,int parent)
{
	assert(a);
	//此时根部为原来的最后一个元素,往下比较
	//即通过父亲去找到自己的孩子,如果孩子比自己小,就得交换位置,如果孩子比自己大,就退出
	//但是因为父亲有一个左孩子parent*2+1,右孩子parent*2+2,我们选择孩子中较小的和自己交换
	int child = parent * 2 + 1;//假设左孩子比右孩子小
	while (child<n)//当child超出个数的时候结束
	{
		if (child+1<n && a[child + 1]<a[child])//如果右孩子比左孩子小,假设错误,修正错误
			//注意,一定不能写反,要注意只有左孩子没有右孩子的情况
			child++;
		if (a[child] < a[parent])//如果孩子小于父亲,交换
		{
			Swap(&a[child], &a[parent]);
			//交换完后,让原来的孩子变成父亲,然后再找新的孩子
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;//如果孩子大于等于父亲,直接退出
	}
}

       在上述算法中,我们应用了先假设再推翻的方法,一开始我们先假设左孩子比较小,然后我们再给个条件判断,如果左孩子大于右孩子,假设不成立,再推翻,这样可以保证我们的child变量一定是较小的孩子!! 

       虽然这里的parent很明显是从a[0]开始,好像不需要专门去传一个parent的参数,但是这也是为了之后的堆排序做准备!

3.8 取堆顶的数据

HPDataType HeapTop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php));//为空的话没有取的必要
	return php->a[0];
}

3.9 堆的数据个数

int HeapSize(Heap* php)
{
	assert(php);
	return php->size;
}

3.10 堆的判空

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

3.11 堆的销毁

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

3.12 堆的打印(测试)

我们要实现堆的打印,利用我们之前封装的函数,每获取一次堆顶元素就删除一次,直到堆删完就可以获取全部的元素了!!

#include"Heap.h"
int main()//该方法实现堆的顺序打印
{
	Heap hp;
	HeapInit(&hp);
	int a[] = { 55,100,70,32,50,60 };
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
		HeapPush(&hp, a[i]);//不断进堆
	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
		printf("%d\n", top);
		HeapPop(&hp);
	}
	HeapDestory(&hp);
	return 0;
}

前面只是先创建一个堆,从while循环开始才是实现对堆的打印!!

运行结果 :32 50 55 60 70 100

          我们发现了一个情况:按道理来说堆只有父子节点之间有大小关系,兄弟之间没有的,但是我们最后打印出来的结果却完成了排序!!!下面我们来进行分析

DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记

     总之任何一个堆,我们都可以通过不断地pop去实现它的顺序打印!!堆排序后面会介绍!

四、堆实现的全部代码

4.1 Heap.h

#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;
}Heap;

void Swap(HPDataType* p1, HPDataType* p2);//实现父亲和孩子的交换
void AdjustUp(HPDataType* a, int child);//向上调整算法

// 堆的初始化
void HeapInit(Heap* php);
// 堆的插入
void HeapPush(Heap* php, HPDataType x);
// 堆的删除
void HeapPop(Heap* php);
// 取堆顶的数据
HPDataType HeapTop(Heap* php);
// 堆的数据个数
int HeapSize(Heap* php);
// 堆的判空
bool HeapEmpty(Heap* php);
// 堆的销毁
void HeapDestory(Heap* php);

4.2 Heap.c

#include"Heap.h"
//当前实现小堆
void HeapInit(Heap* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size = 0;
}

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

void AdjustUp(HPDataType* a, int child)
{
	assert(a);
    //通过孩子找父亲  parent=(child-1)/2
	int parent = (child - 1) / 2;
	//孩子和父亲开始比较,如果孩子小,就交换,如果孩子大,退出循环
	while (child>0)//如果孩子变成了根节点,就没有必要再找了,因为已经没有父母了
		//如果用parent>=0来判断,那么由于(0-1)/2是-1/2,取整后还是0,就会一直死循环,所以必须用孩子来当循环条件
	{
		if (a[child] < a[parent])//孩子小,交换
		{
			Swap(&a[child], &a[parent]);
			//但是交换过后,可能还需要继续往上比,所以我们要让原来的父亲变成孩子,然后再找新的父亲进行比较
			child = parent;
			parent = (child - 1) / 2;
		}
		else//孩子大,退出
			break;
	}
}

void AdjustDown(HPDataType* a, int n,int parent)
{
	assert(a);
	//此时根部为原来的最后一个元素,往下比较
	//即通过父亲去找到自己的孩子,如果孩子比自己小,就得交换位置,如果孩子比自己大,就退出
	//但是因为父亲有一个左孩子parent*2+1,右孩子parent*2+2,我们选择孩子中较小的和自己交换
	int child = parent * 2 + 1;//假设左孩子比右孩子小
	while (child<n)//当child超出个数的时候结束
	{
		if (child+1<n && 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 HeapPush(Heap* php, HPDataType x)
{
	assert(php);
	//首先要判断是否需要扩容
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* temp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);
		if (temp == NULL)
		{
			perror("malloc fail");
			exit(1);
		}
	    //扩容成功
		php->a = temp;
		php->capacity = newcapacity;
	}
     //扩容后,我们插入这个元素并size++
	php->a[php->size++] = x;
	//但是插入之后可能会破坏堆的结构,所以我们需要这个元素和他的父辈进行逐个比较, 
	AdjustUp(php->a,php->size-1);//封装一个向上调整函数,传入数组和新加元素的下标
}

void HeapPop(Heap* php)//一般来说,堆中的删除指的是删除根位置的数据
//如果直接删除根然后往前挪动一位,那么亲缘关系就会十分混乱,为了能够尽量在调整中减少对关系的改变
//我们将根部元素与最后一个元素进行交换之后再删除,此时的根是原先的最后一个元素
//然后将该元素进行向下调整(封装一个函数,传入数组、元素个数、)
{
	assert(php);
	assert(!HeapEmpty(php));//为空的话没有删除的必要
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	//开始向下调整
	AdjustDown(php->a, php->size,0);
}


HPDataType HeapTop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php));//为空的话没有取的必要
	return php->a[0];
}

int HeapSize(Heap* php)
{
	assert(php);
	return php->size;
}

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

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

4.3 test.c(测试)

#include"Heap.h"
int main()//该方法实现堆的顺序打印
{
	Heap hp;
	HeapInit(&hp);
	int a[] = { 55,100,70,32,50,60 };
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
		HeapPush(&hp, a[i]);//不断进堆
	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
		printf("%d\n", top);
		HeapPop(&hp);
	}
	HeapDestory(&hp);
	return 0;
}

五、堆的应用

5.1 堆排序

要对数组排序前,我们要用堆排序,首先要建堆!

大家看看之前堆的打印时的测试代码逻辑的方法

就是我们得到一个数组,就先建堆,然后先把数组push进去,再pop出来,是可以实现有序的

DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记

但是现在我们的需求不是打印出来,而是将他排好序后放进数组里,所以们可以这么写:

void HeapSort(int* a, int n)
{
	HP hp;
	HeapInit(&hp);
	// N*logN
	for (int i = 0; i < n; ++i)
	{
		HeapPush(&hp, a[i]);
	}

	// N*logN
	int i = 0;
	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
		a[i++] = top;
		HeapPop(&hp);
	}

	HeapDestroy(&hp);
}

 这个方法固然是可以的,但是很麻烦,原因如下:

1、每次都要建立一个新的堆,然后再销毁,比较麻烦,而且空间复杂度比较高 

2、我通过把数组放进变成堆,还要再把堆拷贝到数组中,数据的拷贝是很繁琐的!!

所以我们要思考一种方式避免数据的拷贝,所以就有了向上调整建堆和向下调整建堆的方法了!!

也就是我们在原数组的基础上直接建堆,然后向下调整排序即可,下面会详细介绍

5.1.1 向上调整建堆

DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记 假设数组有n个元素

for (int i = 1; i < n; i++)
{
	AdjustUp(a, i);
}

5.1.2 向下调整建堆

DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记

for (int i = (n-1-1)/2; i >= 0; i--)
{
	AdjustDown(a, n, i);
}

5.1.3 堆排序的实现

那我们究竟选择向下建堆好还是向下建堆好呢??我们来分析一下

DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记

DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记

所以我们发现向上调整建堆的时间复杂度大概是N*logN,而向下调整建堆的时间复杂度是N

其实们在推导的时候也能发现,向上调整建堆是节点多的情况调整得多,节点少的情况调整的少,次数是多*多+少*少 ,而向下调整建堆是节点多的情况调整得少,节点少的情况调整的多,次数是多*少+少*多,显然是向下调整建堆是更有优势的!!

     接下去我们建好堆,就要想着怎么去排序了,我们思考一下,之前我们对堆的打印时,不断pop打印出来有序结果的原因是什么??原因就是pop函数里的向下调整算法!!每一次交换根节点和尾节点,将每个节点进行向下调整,最后就可以得到有序的

 DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记

 因为我们之前实现的向下调整算法是小堆的,所以我们这边来实现一个降序的堆排序算法

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 >= 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

 DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记

 如果我们想实现升序,将向下调整算法按照大堆的规则改一下就行 

向下调整算法和向上调整算法的空间复杂度都是(logN) 

堆排序中,建堆的时间复杂度是o(N),排序的时间复杂度是(N*logN)所以堆排序的总时间复杂度是N*logN

5.2 TOP-K问题

Top-k问题:即求数据中前k个最大的元素或者是最小的元素,一般情况下的数据量都比较大!

比如:专业前10名、世界五百强、富豪榜前十

堆排序能够帮助我们在大量数据中筛选出最好的几个。

5.2.1 思路

        比如说我们要从1000个学生的成绩中找到前10个分数最高的,方法就是将所有的数据放在一个数组里,直接建大堆,然后pop9次就可以找到了(pop中的向下调整算法可以使得每次pop出去的都是最大值,然后pop9次的原因是因为第10次就可以直接去获取堆顶元素即可)

但是有些情况,上述思路解决不了,分析:

DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记

5.2.2 通过数组验证TOP-K

void PrintTopK(int* a, int n, int k)
{
	//建前k个建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
		AdjustDown(a, k, i);
	//将剩余n个数据不断与堆顶元素比较,大就交换,然后向下调整
	for (int i = k; i < n; i++)
	{
		if (a[i] > a[0])
		{
			a[0] = a[i];//直接覆盖就行,不用交换
			AdjustDown(a, k, 0);
		}
	}
	//打印
	for(int i=0;i<k;i++)
	printf("%d ", a[i]);
}

void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand((unsigned int)time(NULL));
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;//随机数范围0-999999
	}
// 为了能够方便找到这些数
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	PrintTopK(a, n, 10);
}

int main()
{
	TestTopk();
	return 0;
}

DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记

5.2.3 通过文件验证TOP-K

其实用数组的方法,并不能有效地模拟,我们可以尝试用文件的方式来验证

void CreateNDate()
{
	// 造数据
	int n = 10000;
	srand((unsigned int)time(NULL));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (size_t i = 0; i < n; ++i)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);//将随机数写进文件
	}
	fclose(fin);
}

void PrintTopK(int k)
{
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}

	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL)
	{
		perror("malloc fail");
		return;
	}

	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);//从文件读取数据
	}

	// 建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, k, i);
	}

	int val = 0;
	while (!feof(fout))//feof是文件结束的标识,如果返回1,则说明文件结束
	{
		fscanf(fout, "%d", &val);//fscaf的光标闪动到原先的位置,所以会从k的位置开始读
		if (val > kminheap[0])
		{
			kminheap[0] = val;
			AdjustDown(kminheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("\n");
}
int main()//该方法实现堆的顺序打印
{
	CreateNDate();
	PrintTopK(5);
	return 0;
}

友友们上述代码有不理解的,看看博主关于文件操作里的函数介绍:

C语言:文件操作详解-CSDN博客

DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记 不太好找,所以我们可以先注释创造数据的文件,然后再文件中修该出5个最大数,然后再执行一次函数

DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记

以上就是通过数组验证top和利用文件验证tok的方法!!

 DS:二叉树的顺序结构及堆的实现,数据结构,开发语言,数据结构,c语言,笔记文章来源地址https://www.toymoban.com/news/detail-827708.html

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

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

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

相关文章

  • 【完全二叉树魔法:顺序结构实现堆的奇象】

    二叉树的顺序结构 堆的概念及结构 堆的实现 堆的调整算法 堆的创建 堆排序 TOP-K问题         普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储

    2024年02月07日
    浏览(39)
  • 【数据结构】树、二叉树的概念和二叉树的顺序结构及实现

    之前我们学习了顺序表、链表以及栈和队列这些数据结构,但这些数据结构都是线性的(一对一)。接下来要学习 非线性的数据结构——树(二叉树) ,相比前面的,树的结构更加复杂,话不多说,直接进入正题吧。 树是一种 非线性的数据结构 ,它是 一对多(也有可能是

    2024年02月07日
    浏览(42)
  • 【数据结构】二叉树的顺序结构及实现

    目录 1. 二叉树的顺序结构 2. 堆的概念及结构 3. 堆的实现 3.1 堆向下调整算法 3.2 堆的创建 3.3 建堆时间复杂度 3.4 堆的插入 3.5 堆的删除 3.6 堆的代码实现 4. 堆的应用 4.1 堆排序 4.2 TOP-K问题 普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉

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

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

    2024年02月08日
    浏览(45)
  • 二叉树的顺序结构及实现(堆、Top-k)

    1 二叉树的顺序结构 2 堆的概念及结构 3 堆的实现 4 堆的应用 1 二叉树的顺序结构        普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要

    2024年02月11日
    浏览(33)
  • 【数据结构】二叉树的顺序结构实现及时间复杂度计算(二)

    目录 一,二叉树的顺序结构实现         1,二叉树的顺序结构         2,堆的概念及结构         3,堆的接口实现 1,堆的创建 2,接口函数 3,初始化 4,销毁 5,是否增容 6,交换数据 7,堆向上调整算法 8,插入数据 9,删除数据 10,堆向下调整算法 11,打印数

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

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

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

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

    2023年04月21日
    浏览(45)
  • 【数据结构】二叉树的顺序结构-堆

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

    2024年02月09日
    浏览(53)
  • 数据结构:二叉树的顺序结构--堆

    朋友们、伙计们,我们又见面了,本期来给大家解读一下二叉树--堆的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏:C语言:从入门到精通 数据结构专栏:数据结构 个  人  主  页 :stackY、 目录 前言: 1.堆的概念及

    2024年02月06日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包